一、时间复杂度
1)时间复杂度是衡量算法执行时间随输入规模增长的增长率。
2)通过分析算法中基本操作的执行次数来确定时间复杂度。
3)常见的时间复杂度包括：常数时间O(1)，线性时间O(n), 对数时间O(log n)，平方时间O(n^2)等。
4)在计算的时候我们关注的是复杂度的数量级，并不要求严格的表达式。
一般我们关注的是最坏时间复杂度，用O(f(n))表示，大多数时候我们仅需估算即可。
一般来说，评测机1秒大约可以跑2e8次运算，我们要尽可能地让我们的程序运算规模的数量级控制在1e8以内。
二、空间复杂度
1)空间复杂度是衡量算法执行过程中所需的存储空间随输入规模增长的增长率。
2)通过分析算法中所使用的额外存储空间的大小来确定空间复杂度。
3)常见的空间复杂度包括：常数空间O(1)，线性空间O(n)，对数空间O(log n)，平方空间O(n^2)等。
一般我们关注的是最坏空间复杂度，用O(f(n)表示，大多数时候程序占用的空间一般可以根据开的数组大小精确算出，但也存在需要估算的情况。题目一般不会卡空间，一般是卡时间。举个例子，假如题目限制128MB,1int32bit4Bytes,128MB32*2^20int~3e7int
三、分析技巧
- 理解基本操作：基本操作可以是算术运算(加法，乘法，位运算等)，比较操作，赋值操
- 作等。
- 关注循环结构：循环是算法中常见的结构，它的执行次数对于时间复杂度的分析至关重要。
- 递归算法：递归算法的时间和空间复杂度分析相对复杂。需要确定递归的深度以及每个递
归调用的时间和空间开销。 - 最坏情况分析：对于时间复杂度的分析，通常考虑最坏情况下的执行时间。要考虑输入数据使得算法执行时间达到最大值的情况。
- 善用结论：某些常见算法的时间和空间复杂度已经被广泛研究和证明。可以利用这些已知结果来分析算法的复杂度。
四、相关总结
4.2.1常数复杂度 𝑂(1)
不管数据多大，都是固定时间完成。常数复杂度
// 获取数组第一个元素
int getFirst(int a[], int n) {return a[0]; // 只要1步，跟n没关系
}// 判断一个数是否为偶数
bool isEven(int x) {return x % 2 == 0; // 1步搞定
}
4.2.2对数复杂度 𝑂(log𝑛)
每一步都把问题规模砍掉一半！
// 二分查找：在有序数组中找目标值
int binarySearch(int a[], int n, int target) {int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (a[mid] == target) return mid; // 找到了else if (a[mid] < target) l = mid + 1; // 去右半边找else r = mid - 1; // 去左半边找}return -1; // 没找到
}
搜索范围由n，n/2，n/4，……，n/2^k=1，k=log2 n，复杂度就是 O(logn)。
4.2.3线性复杂度 𝑂(𝑛) - 一遍扫描
需要把每个数据看一遍。
// 找数组中的最大值
int findMax(int a[], int n) {int maxVal = a[0];for (int i = 1; i < n; i++) { // 循环n-1次if (a[i] > maxVal) {maxVal = a[i];}}return maxVal;
}// 计算数组元素之和
int sum(int a[], int n) {int s = 0;for (int i = 0; i < n; i++) { // 循环n次s += a[i];}return s;
}
Tips：一层循环，循环 n 次 → O(n)
4.2.4线性对数复杂度 O(nlogn)
经典代表：归并排序、快速排序、堆排序
// 归并排序的合并函数
void merge(int a[], int l, int mid, int r) {int temp[r - l + 1]; // 临时数组int i = l, j = mid + 1, k = 0;// 合并两个有序部分while (i <= mid && j <= r) {if (a[i] <= a[j]) temp[k++] = a[i++];else temp[k++] = a[j++];}// 处理剩余元素while (i <= mid) temp[k++] = a[i++];while (j <= r) temp[k++] = a[j++];// 复制回原数组for (i = l; i <= r; i++) {a[i] = temp[i - l];}
}// 归并排序主函数
void mergeSort(int a[], int l, int r) {if (l < r) {int mid = (l + r) / 2;mergeSort(a, l, mid); // 排序左半部分mergeSort(a, mid + 1, r); // 排序右半部分merge(a, l, mid, r); // 合并结果}
}
4.2.5平方复杂度 O(n^2)- 双重循环
最容易写出的复杂度。
// 冒泡排序：相邻元素两两比较
void bubbleSort(int a[], int n) {for (int i = 0; i < n; i++) { // 外层循环n次for (int j = 0; j < n - i - 1; j++) { // 内层循环n-i-1次if (a[j] > a[j + 1]) {// 交换a[j]和a[j+1]int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}// 找出数组中所有的数对
void findAllPairs(int a[], int n) {for (int i = 0; i < n; i++) { // 外层循环for (int j = i + 1; j < n; j++) { // 内层循环printf("(%d, %d)\n", a[i], a[j]);}}
}
4.2.6立方复杂度 O(n^3) - 三重循环
// Floyd-Warshall算法：求任意两点间最短路径
void floyd(int dist[][MAXN], int n) {for (int k = 0; k < n; k++) { // 中转点for (int i = 0; i < n; i++) { // 起点for (int j = 0; j < n; j++) { // 终点if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}
}
4.2.7 指数复杂度 O(2^n) - 暴搜噩梦
// 递归求斐波那契数列（低效版本）
int fib(int n) {if (n <= 1) return n;return fib(n-1) + fib(n-2); // 每次分成两个子问题
}
4.2.8特殊：调和级数复杂度 O(nlog n)
这是一个容易被忽略但很重要的复杂度：
// 统计所有因数对的数量
int countDivisors(int n) {int cnt = 0;for (int i = 1; i <= n; i++) { // 外层循环n次for (int j = i; j <= n; j += i) { // 内层：i的倍数cnt++;}}return cnt;
}
