常见的时间复杂度

常见的时间复杂度量级有：

复杂度	记作	复杂度	记作
常数阶	$O(1)$	平方阶	$O(n^2)$
对数阶	$O(log n)$	立方阶	$O(n^3)$
线性阶	$O(n)$	K次方阶	$O(n^k)$
线性对数阶	$O(n log n)$	指数阶	$O(2^n)$

他们的时间复杂度越来越大，执行的效率越来越低。

常数阶$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(logn)$

同样是 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......2^x$，也就是当 2 的 x 次方大于 n 时，跳出循环，因此$log n$， 程序执行了$log n$次，时间复杂度为：$O(log n)$

线性对数阶$O(nlogn)$

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

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

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

平方阶$O(n^2)$

平方阶$O(n2)$就更容易理解了，如果把$O(n)$的代码再嵌套循环一遍，它的时间复杂度就是$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^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!)$，效率很低。

---

常见算法的时间复杂度

算法

• 二分查找(Binary Search)：$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)logn)$，是一种用于求解单源最短路径的贪心算法，常用于带有非负权重边的图。
  
  

• 动态规划(Dynamic Programming)：时间复杂度因问题而异 动态规划算法的时间复杂度取决于具体问题和子问题的数量。通常，动态规划算法会填充一个表格，时间复杂度与填充该表格所需的操作次数成正比。
  
  

函数

• sqrt(n)： 计算 n 的平方根。时间复杂度为$O(logn)$，采用二分法等快速算法实现。
  
  

• sort(a, a+n)： 对数组 a 进行排序。时间复杂度为$O(nlogn)$，采用快速排序、归并排序等常用排序算法实现。
  
  

• __gcd(a, b)： 计算 a 和 b 的最大公约数。时间复杂度为$O(logmin(a,b))$，采用辗转相除法实现。
  
  

• pow(x, n)： 计算 x 的 n 次方。时间复杂度为$O(logn)$，采用快速幂算法。
  
  

• abs(x)： 返回 x 的绝对值。时间复杂度为$O(1)$。
  
  

• log(x)、log10(x)、log2(x)： 计算 x 的自然对数、以 10 为底的对数、以 2 为底的对数。时间复杂度为$O(1)$。
  
  

char数组

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

• strlen(a)： 返回字符串 a 的长度。时间复杂度为$O(n)$。
  
  

• strcpy(a, b)： 将字符串 b复制到 a中。时间复杂度为$O(n)$，其中 n 为字符串 b的长度。
  
  

• strcat(a, b)： 将字符串 a连接到 b的末尾。时间复杂度$O(n)$，其中 n 为字符串 a的长度。
  
  

• strcmp(a, b)： 比较字符串 a和 b的大小关系。时间复杂度为$O(n)$，其中 n 为字符串 a和 b的长度的较小值。
  
  

string

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

• length()/size(): $O(1)$，即常数时间复杂度。这是因为字符串的长度是在构造函数中计算得到的，并且在字符串的操作过程中一直被维护着。
  
  

• append(): $O(n)$，其中 n 是要追加的字符串的长度。因为要将追加的字符串复制到原字符串的末尾，所以时间复杂度为 $O(n)。
  
  

• insert(): $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(n)$。
  
  

• erase(): $O(1) ~ O(n)$，具体取决于删除位置和链表的长度。在链表中删除元素时，只需要调整链表中相应的指针即可，因此时间复杂度为$O(1)$。但如果删除位置比较靠后，删除操作需要遍历一部分链表，因此时间复杂度会变成 $O(n)$。
  
  

• size(): $O(1)$，即常数时间复杂度。这是因为链表中维护了一个变量来记录元素个数，可以直接返回。
  
  

• reverse(): $O(n)$，其中 n 是链表的长度。reverse 函数需要将链表中所有元素倒序排列，因此需要遍历一遍链表，时间复杂度为 $O(n)$。