常见的时间复杂度

常见的时间复杂度

常见的时间复杂度量级有：常数阶O(1)，对数阶O(log⁡ n)，线性阶O(n)，线性对数阶O(n log⁡ n)，平方阶O(n^2)O，立方阶O(n^3)，K次方阶O(n^k)，指数阶O(2^n)O。他们的时间复杂度越来越大，执行的效率越来越低。

下面选取一些较为常用的来讲解一下。

常数阶O(1)

代码执行次数是一个常数，不随n的变化而变化，那这个代码的时间复杂度就都是O(1)，如下的代码中虽然含有for循环，但循环次数是100次，不随问题规模变化而变化，因此是常数级O(1)的时间复杂度：

for(int i = 1; i <= 100; i++){
    sum += i;
}

线性阶O(n)

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

for(int i = 1; i <= n; i++){
    sum += i;
}

对数阶O(log⁡ n)

同样是for循环，但这段代码的时间复杂度是O(log⁡ n)，因此不能单纯认为for循环就一定是O(n)的。

for(int i = 1; i <= n; i *= 2){
    cnt++;
}

在这个for循环里，i 开始是1，然后不是自增1，而是自乘2，因此i的值依次是1、2、4、8……2x1、2、4、8…… 2^x1、2、4、8……2x ，也就是当2的x次方大于n时，跳出循环，因此x =log⁡n \log nlogn，程序执行了log⁡n \log nlogn次，时间复杂度为：O(log⁡ n)

线性对数阶O(n log⁡ n)

线性对数阶O(n log⁡ n) 其实非常容易理解，将时间复杂度为O(log⁡ n) 的代码循环n遍的话，那么它的时间复杂度就是 n×O(log⁡n)n \times O(\log n)n×O(logn)。

就拿上面的代码加一点修改来举例：

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j *= 2){
        cnt++;
    }
}

平方阶O(n^2)O

平方阶O(n2)O(n^2) O(n2)就更容易理解了，如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是 O(n2)O(n^2) O(n2) 了。

for(int i = 1; i <= n; i++){
   for(int j = 1; j <= n; j++){
        cnt++;
    }
}

其实冒泡排序的时间复杂度也是O(n^2^)，以下代码中，当i=1时，执行n-1次，i=2时，执行n-2次……因此总的执行次数也就是 (n-1)+(n-2)…+2+1就是n*(n-1)/2，显然n^2^的量级更大，因此常数项和n/2可以忽略，时间复杂度即为O(n^2^)：

for(int i =1; i<=n; i++){
   for(int j=1; j<=n-i; j++){
        if(a[j] > a[j+1]) 
            swap(a[j], a[j+1]);
    }
}

阶乘 O(n!)

比如用枚举的方法求1~n的全排列，时间复杂度是 O(n!)O(n!)O(n!)，效率很低。

📜历年真题

1/5填空题（14分）全站正确率 25%

完善程序：
（序列重排）全局数组变量 aaa 定义如下：

const int SIZE = 100;
int a[SIZE], n;

它记录着一个长度为nn n的序列 a[1],a[2],⋯,a[n]a[1], a[2], ⋯ , a[n]a[1],a[2],⋯,a[n]。
现在需要一个函数，以整数p(1≤p≤n)p (1 ≤p ≤n) p(1≤p≤n)为参数，实现如下功能：将序列aaa 的前p pp个数与后n–p n –pn–p 个数对调，且不改变这ppp 个数（或n–pn –p n–p个数）之间的相对位置。例如，长度为 5 的序列 1, 2, 3, 4, 5，当p\=2 p = 2p\=2 时重排结果为3, 4, 5, 1, 2 。
有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)O( n)O(n)、空间复杂度为 O(n)：

void swap1( int p )
{
    int i, j, b[SIZE];
    for ( i = 1; i <= p; i++ )
        b[①] = a[i];     
    for ( i = p + 1; i <= n; i++ )
        b[i - p] = ②;     
    for ( i = 1; i <= ③; i++ ) 
        a[i] = b[i];
}

我们也可以用时间换空间，使用时间复杂度为O(n^2)O、空间复杂度为O(1)O(1) O(1)的算法：

void swap2(int p)
{
    int i, j, temp;
    for ( i = p + 1; i <= n; i++ )
    {
        temp = a[i];
        for ( j = i; j >= ④; j-- ) 
            a[j] = a[j - 1];
        ⑤ = temp;   
    }
}

常见算法的时间复杂度

算法

二分查找（Binary Search）：O(logn)O(log n)O(logn) 二分查找算法每次将搜索区间缩小一半，因此时间复杂度为O(log n)。
倍增法（Exponentiation by Squaring）：O(log n) 倍增法用于快速计算幂，如 a^n。每次迭代将幂指数减半，因此时间复杂度为O(log n)。
深度优先搜索（Depth-First Search，DFS）：O(V+E) 深度优先搜索遍历图的时间复杂度为O(V+E)，其中V表示顶点数，E表示边数。
广度优先搜索（Breadth-First Search，BFS）：O(V+E) 和深度优先搜索类似，广度优先搜索遍历图的时间复杂度为O(V+E)，其中V表示顶点数，E表示边数。
快速排序（Quick Sort）：平均情况下 O(n log n)，最坏情况下 O(n^2) 快速排序算法的平均时间复杂度为O(n log n)，但最坏情况下（极度不平衡的划分）可能达到O(n^2)。
归并排序（Merge Sort）：O(n log n) 归并排序算法的时间复杂度为O(n log n)，因为它将数组分成两半，并递归地排序它们，然后将它们合并。
迪杰斯特拉(Dijkstra)： O((n+m)log⁡n)O((n + m) \log n)O((n+m)logn)，是一种用于求解单源最短路径的贪心算法，常用于带有非负权重边的图。
动态规划（Dynamic Programming）：时间复杂度因问题而异动态规划算法的时间复杂度取决于具体问题和子问题的数量。通常，动态规划算法会填充一个表格，时间复杂度与填充该表格所需的操作次数成正比。

函数

sqrt(n)：计算 nnn 的平方根。时间复杂度为 O(log⁡ n)，采用二分法等快速算法实现。
sort(a, a+n)：对数组 aaa 进行排序。时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，采用快速排序、归并排序等常用排序算法实现。
__gcd(a, b)：计算 aaa 和 bbb 的最大公约数。时间复杂度为 O(log⁡min⁡(a,b))O(\log \min(a, b))O(logmin(a,b))，采用辗转相除法实现。
pow(x, n)：计算 xxx 的 nnn 次方。时间复杂度为 O(log⁡ n)，采用快速幂算法。
abs(x)：返回 xxx 的绝对值。时间复杂度为 O(1)。
log(x)、log10(x)、log2(x)：计算 xxx 的自然对数、以 10 为底的对数、以 2 为底的对数。时间复杂度为 O(1)。

char数组

以下是常见的一些 char 数组函数及其时间复杂度：

strlen(a)：返回字符串 a 的长度。时间复杂度为 O(n)。
strcpy(a, b)：将字符串 b复制到 a中。时间复杂度为 O(n)，其中 nnn 为字符串 b的长度。
strcat(a, b)：将字符串 a连接到 b的末尾。时间复杂度为 O(n)，其中 nnn 为字符串 a的长度。
strcmp(a, b)：比较字符串 a和 b的大小关系。时间复杂度为 O(n)，其中 nnn 为字符串 a和 b的长度的较小值。

string

string是一个常用的字符串类，以下是几个常用函数的时间复杂度：

length()/size(): O(1)，即常数时间复杂度。这是因为字符串的长度是在构造函数中计算得到的，并且在字符串的操作过程中一直被维护着。
append(): O(n)，其中 n 是要追加的字符串的长度。因为要将追加的字符串复制到原字符串的末尾，所以时间复杂度为 O(n)。
insert():O(n) O(n)O(n)，其中 n 是要插入的字符串的长度。因为要将插入位置后面的字符串往后移动，所以时间复杂度为 O(n)。
erase(): O(n)，其中 n 是要删除的字符串的长度。因为要将删除位置后面的字符串往前移动，所以时间复杂度为 O(n)。
find(): O(n)，其中 n 是字符串的长度。因为 find() 函数需要遍历整个字符串来查找子串，所以时间复杂度为 O(n)。

list

list 是一个双向链表容器，用于存储和操作一组数据。以下是 list 中常见函数的时间复杂度：

push_front()/pop_front(): O(1)，即常数时间复杂度。这是因为链表头节点的地址已知，可以直接进行头插和头删操作。
push_back()/pop_back(): O(1)，即常数时间复杂度。这是因为链表尾节点的地址已知，可以直接进行尾插和尾删操作。
insert(): O(1) ~ O(n)，具体取决于插入位置和链表的长度。在链表中插入元素时，只需要调整链表中相应的指针即可，因此时间复杂度为O(1) O(1)O(1)。但如果插入位置比较靠后，插入操作需要遍历一部分链表，因此时间复杂度会变成O(n) O(n)O(n)。
erase(): O(1) ~ O(n)，具体取决于删除位置和链表的长度。在链表中删除元素时，只需要调整链表中相应的指针即可，因此时间复杂度为 O(1)。但如果删除位置比较靠后，删除操作需要遍历一部分链表，因此时间复杂度会变成 O(n)。
size(): O(1)，即常数时间复杂度。这是因为链表中维护了一个变量来记录元素个数，可以直接返回。
reverse(): O(n)，其中 n 是链表的长度。reverse 函数需要将链表中所有元素倒序排列，因此需要遍历一遍链表，时间复杂度为 O(n)。

DAY10-算法复杂度分析