常见算法的时间复杂度
算法
- 二分查找（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)。