# Big O Notation 大O表示法是**算法复杂度分析**的核心工具，用于描述算法执行时间或空间随输入规模增长的**上界**。它关注的是当输入规模 n 趋向无穷大时，算法性能的增长趋势。我们使用大O表示法去描述算法的性能 ### 核心思想 - **忽略常数因子**：O(2n) = O(n) - **忽略低阶项**：O(n² + n) = O(n²) - **关注最坏情况**：保证在任何情况下都不会超过这个界限 ## O(1) - 常数时间 ```c++ // 无论输入多大，执行时间固定 int getFirstElement(int arr[], int n) { return arr[0]; // 只访问一次 } int sum = a + b; // 基本运算 bool flag = true; // 赋值操作 ``` ## O(n) - 线性时间 ```c++ // 遍历数组 int findMax(int arr[], int n) { int maxVal = arr[0]; for (int i = 1; i < n; i++) { // 执行 n-1 次 if (arr[i] > maxVal) maxVal = arr[i]; } return maxVal; } // 单层循环 for (int i = 0; i < n; i++) { cout << arr[i] << " "; } ``` ## o(n²) - 平方时间 ```c++ // 冒泡排序 void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { // n 次 for (int j = 0; j < n - i - 1; j++) { // 平均 n/2 次 if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]); } } } // 双重嵌套循环 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << arr[i][j] << " "; // 执行 n² 次 } } ``` ## O(logn) - 对数时间 ```c++ // 二分查找 int binarySearch(int arr[], int n, int target) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } // 每次将问题规模减半 while (n > 1) { n = n / 2; // log₂n 次循环 } ``` ## O(2ⁿ) ```c++ // 递归求斐波那契数列（朴素版本） int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n-1) + fibonacci(n-2); // 每个调用产生两个子调用 } // 递归树有 2ⁿ 个节点 // 子集枚举 void generateSubsets(int n, vector& current, int index) { if (index == n) { print(current); // 处理一个子集 return; } generateSubsets(n, current, index + 1); // 不选 current.push_back(index); generateSubsets(n, current, index + 1); // 选 current.pop_back(); } ``` ## O(n!) ```c++ // 全排列生成 void permute(vector& nums, int start) { if (start == nums.size()) { print(nums); // 输出一个排列 return; } for (int i = start; i < nums.size(); i++) { swap(nums[start], nums[i]); permute(nums, start + 1); // n! 种排列 swap(nums[start], nums[i]); } } ``` ## 复杂度对比表 |复杂度|名称|n=10|n=100|n=1000|典型算法| |:-:|:-:|:-:|:-:|:-:|:-:| |O(1)|常数|1|1|1|数组访问| |O(log n)|对数|3|7|10|二分查找| |O(n)|线性|10|100|1000|遍历| |O(n log n)|线性对数|33|664|9966|快排、归并| |O(n²)|平方|100|10,000|1,000,000|冒泡排序| |O(n³)|立方|1,000|1,000,000|10⁹|Floyd算法| |O(2ⁿ)|指数|1,024|10³⁰|-|暴力搜索| |O(n!)|阶乘|3.6M|-|-|全排列| ## 信奥中的实用建议对于 CSP-J/S、NOIP 等竞赛： - **n ≤ 10⁶**：需要 O(n) 或 O(n log n) - **n ≤ 5000**：可以接受 O(n²) - **n ≤ 500**：可以考虑 O(n³) - **n ≤ 20**：可以用 O(2ⁿ) 状压DP - **n ≤ 10**：可以用 O(n!) 暴力枚举 >**关键技巧**：在竞赛中，先根据数据范围反推可接受的复杂度，再设计算法！ # 空间复杂度(Space Complexity) 空间复杂度描述算法在运行过程中**临时占用存储空间的大小**随输入规模 n 的变化趋势。它包括： - **辅助空间**：算法额外申请的变量、数组等 - **递归栈空间**：递归调用时的函数栈帧 >**注意**：通常不计算输入数据本身占用的空间，只关注算法执行过程中**额外**需要的空间。

01 - 时间复杂度