2022/7/18 笔记 - 时间复杂度 & 列表排序

1. 时间复杂度用 O ( ) O( ) O() 来表示，代表程序运行大概需要的次数，用来评价一个算法
2. 时间复杂度省略常数项，仅保留最高次项
3. 常见的时间复杂度： O ( 1 ) 、 O ( l o g n ) 、 O ( n ) 、 O ( n 2 ) 、 O ( 2 n ) O(1)、O(log n)、O(n) 、O(n^2)、O(2^n) O(1)、O(logn)、O(n)、O(n2)、O(2n)

时间复杂度: O ( n ) O(n) O(n)
仅能用于对较小整数进行排序或统计出现次数

代码实现：

// 0 <= 数字 <= 1000
// bucket 代表桶，下标对应这个数字出现次数
// n 代表数字数量
int t; // 临时变量
for (int i=1; i<=n; i++)
{
    scanf("%d", &t);
    bucket[t]++;
}
// 输出 - 查看每一个数出现的次数 (对应下标的值)
for (int i = 0; i <= 1000; i++)
    if (bucket[i] != 0)
        // 输出 出现次数 次
        for (int j = 0; j < bucket[i]; j++)
            printf("%d ", i);

C++ 自带排序 - 快速排序

最坏时间复杂度 O ( n 2 ) O(n^2) O(n2)，平均时间复杂度 O ( n ∗ l o g n ) O(n*log n) O(n∗logn)

sort() 函数位于头文件内

使用方法：

// 1. 对于默认类型， 从小到大排序
sort(起始地址, 结束地址);
// 如：
int a[10] = {1, 2, 3, 4, 5, 0};
sort(a, a+6);

// 2. 定义比较函数
sort(起始地址, 结束地址, 比较函数名);
// 比较函数返回 bool 类型，传入两个参数，类型是比较对象的类型
// 从大到小排序
bool cmp(int a, int b)
{
    return a > b; // 排序后列表前一个元素与后一个元素之间一定满足此关系
}
int a[10] = {1, 2, 3, 4, 5, 0};
sort(a, a+6, cmp);
// sort 函数无返回值，直接改变原数组