算法效率：时间复杂度的定义与计算 作者：马育民 • 2025-04-06 23:39 • 阅读：10011 # 介绍 时间复杂度描述了算法运行时间随数据规模增长的变化趋势 # 渐进时间复杂度 由于许多情况下要精确计算时间复杂度是困难的，因此引入了渐进时间复杂度:在数量上 **估计一个算法的基本操作总数**。 一般讲时间复杂度，就是渐进时间复杂度。 ### 渐进表示法 使用大 `O` 渐进表示法： - 保留最高阶项（高次项对于函数的增长速度的影响是最大的）：例如 `T(n) = 3n² + 2n + 10` 的时间复杂度为` O(n²)`。 - 忽略常数系数：例如 `T(n) = 2n` 的时间复杂度为 `O(n)` - 常数项用 `1` 表示（常数项对函数的增长速度影响并不大）：例如 `T(n) = 100` 的时间复杂度为 `O(1)` ### 注意 `o(n/2)` 写成 `o(n)` 因为这两者对于大O表示法表示的时间复杂度来说没区别，大O表示法表示的时间复杂度关注的是 **数据量的增长** 导致的 **时间增长情况** `o(n/2)` 和 `o(n)` 在 **数据量增加一倍** 的时候，**时间开销都是增加一倍**（线性增长），所以都认为是O(n) # 常见时间复杂度 ### 总结 - `O(1)`：数组随机访问 - `O(log₂n)`：二分查找、快速幂 - `O(n)`：单层循环遍历数组 - `O(nlog₂n)`：归并排序、堆排序 - `O(n²)`：两层循环 - `O(n³)`：冒泡排序、选择排序 - `O(2ⁿ)`：判断是否包含指定子序列，LCS最长公共子序列钢管切割问题，动态规划法自顶向下。 - `O(n!)`： **提示：** `log₂n` 是 对数，详见 [链接](https://www.malaoshi.top/show_1IX3cskiMR5N.html "链接") ### 对比 `O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)` **提示：**可将 `10` 或 `100` 代入，就能快速算出结果 ### 复杂度 O(1) 例子 1. 单个语句 如: ``` k=0; ``` 2. 整个程序都 **只有顺序执行的语句**，没有循环语句，或复杂函数的调用 ``` char*x="ABCADAB"; int m = strlen(x); printf("len:%d\n",m); ``` ### 复杂度 O(n) 例子 单层循环 ``` for(int i=0 ; i<1 ;i++){ printf(i); } ``` ### 复杂度 O(n²) 例子 两层循环 ``` for(int i=0 ; i<1 ;i++){ for(int j=0 ; j<1 ;j++){ printf("%d-%d",i,j); } } ``` ### 复杂度 O(log₂n) 例子 [二叉树](https://www.malaoshi.top/show_1IX3cuEhaM1S.html "二叉树") ### 复杂度 O(2ⁿ) 例子 判断是否包含指定子序列 如：字符串 `abc` 有多少个子序列？ 答：有以下个子序列 `a` `b` `c` `ab` `ac` `bc` 总结：`2³ - 2 `，渐进法表示：`2ⁿ` # 题 求解两个长度为n的序列 `X` 和 `Y`的一个 **最长公共子序列**（如序列 `ABCBDAB` 和 `BDCABA` 的一个最长公共子序列为 `BCBA` ）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（ ） 经分析发现该问题具有最优子结构，可以定义序列长度分别为 `i` 和 `j` 的两个序列 `X` 和 `Y` 的最长公共子序列的长度为 `C[i]`，如下式所示 [](https://www.malaoshi.top/upload/0/0/1GWuoKbnu4d.png) 采用 **自底向上** 的方法实现该算法，则时间复杂度为( ) A、O(n²) B、O(n²lgn) C、O(n³) D、O(n2ⁿ) A、O(n²) B、O(n²lgn) C、O(n³) D、O(n2ⁿ) ### 第一问分析 **子序列解释：**与子串类似，但子序列不要求连续 求第一个序列的子序列的个数，时间复杂度：`2ⁿ`，排除 A、B、C 判断上面的子序列是否在第二个序列中，时间复杂度：`n` 所以是：`n * 2ⁿ`， ### 第一问答案 D ### 第二问分析 具体没看懂，但从公式中的 `C[i][j]` 可知，这是二维数组，而且有3个判断条件： - 第一、第二判断条件简单，可忽略 - 第三个判断条件：当 `其它` 时，求最大值 `max(C[i-1,j],C[i,j-1])` - 自底向上：表示从 `C[0][0]` 算到 `C[最大值][最大值]` ，由此可知，需要 **两层循环**，所以时间复杂度是 `n²` ### 第二问答案 A 参考： https://blog.csdn.net/2503_90358233/article/details/146294672 https://zhidao.baidu.com/question/245509450.html 原文出处：http://malaoshi.top/show_1GWtjNqqtCm.html