算法复杂度：时间复杂度（算法效率）

作者：马育民 • • 阅读：10118

提出问题

如何测算不同算法运行时间？最直接的方法就是在计算机上运行一下程序，测试运行的时间。但是，受计算机硬件（CPU、内存、硬盘）、编程语言等影响，就算执行相同的算法，运行的时间也也不相同

解决

使用 时间复杂度

介绍

时间复杂度（Time Complexity） 是算法分析中用于量化算法运行时间随输入数据规模增长趋势的核心概念，它描述的是 算法执行步骤 与输入规模 n 的函数关系，重点关注增长量级，而 非具体耗时，是评估算法效率的关键指标。

定义

时间复杂度 不计算 算法的 绝对运行时间（受硬件、编程语言、环境影响），而是通过 统计算法中基本操作（如赋值、比较、算术运算）的执行次数，推导其与输入规模 n 的渐近关系，用 大 O 表示法（Big O Notation） 规范表达，形式为 O(f(n))，其中 f(n) 是关于 n 的函数，代表操作次数的增长量级。

如何计算算法的时间复杂度

时间复杂度指算法运行需要的 时间。一般将算法的基本运算 执行次数 作为时间复杂度的度量标准。

例子

看下面程序，各个语句执行的次数

int sum(int n){
    int sum=0; //1次
    for（int i=1;i<=n;i++) //n+1次
        sum+=i; //n次
    return sum; //1次
}

总的执行次数为 2×n+3 。

如果用一个函数 T(n) 表达：T(n)=2n+3，则当 n 足够大时，例如 n=105 时，T(n)=2×105+3。

算法运行时间主要 取决于最高项，后面的可以忽略不计。

因为如果你告诉朋友买车花了20万零199元，大家都认为是20万元，没有人关心后面的尾数。如果一个人是亿万富翁，那么不管其有2亿元还是10亿元，都是亿万富翁。

因此在表达时舍小项、舍系数，只看最高项就可以了。如果用时间复杂度的渐进上界 O 表示，那么该算法的时间复杂度为 O(n)，这就是 渐进时间复杂度

例子2

其实完全没有必要计算每一行代码的运行次数，只需计算 语句频度最多 的即可。循环内层的语句往往是运行次数最多的，对运行时间贡献最大。

例如：在下面的算法中，total=total+i*j 是对算法贡献最大的语句，只计算该语句的运行次数即可。该算法的时间复杂度为 O(n2)

sum=0;        //运行1次
total=0;    //运行1次
for(i=l;i<=n;i++){        //运行 n+1 次，最后 1 次判断条件不成立，结束
    sum=sum+i;            //运行 n 次
    for(j=1;j<=n;j++)     //运行 n*(n+1)次
        total=total+i*j;  //运行 n*n 次
}

最好、最坏和平均情况

并不是对每个算法都能直接计算运行次数。有些算法如排序、查找、插入等，可以按最好、最坏和平均情况分别求算法渐进复杂度。但在考察一个算法时，我们通常考察最坏的情况是怎样的，而不是考察最好的情况，最坏的情况对于衡量算法的好坏具有实际意义。

渐进时间复杂度

由于许多情况下要精确计算时间复杂度是困难的，因此引入了渐进时间复杂度:在数量上 估计一个算法的基本操作总数。

一般讲时间复杂度，就是渐进时间复杂度。

渐进表示法

推导时间复杂度时，遵循 渐近上界 原则，只保留 增长最快 的项，忽略 低阶项 和 常数系数，规则如下：

  1. 忽略常数项：若操作次数为 n + 5，时间复杂度为 O(n)（常数 5 随 n 增大可忽略）；

  2. 忽略低阶项：若操作次数为 n^2 + 3n + 2，时间复杂度为 O(n^2)（n^2 增长远快于 3n 和 常数2 ）；

  3. 忽略常数系数：若操作次数为 2n，时间复杂度为 O(n)（系数 2 不影响增长量级）；

  4. 嵌套结构相乘：嵌套循环的操作次数为各层循环次数的乘积，如两层嵌套循环次数为 n \times n，复杂度为 O(n^2)

注意

o(n/2) 写成 o(n)

因为这两者对于大O表示法表示的时间复杂度来说没区别，大O表示法表示的时间复杂度关注的是 数据量的增长 导致的 时间增长情况

o(n/2) 和 o(n) 在 数据量增加一倍 的时候，时间开销都是增加一倍（线性增长），所以都认为是O(n)

常见时间复杂度

总结

复杂度表示 名称 核心特征 典型场景 增长趋势
O(1) 常数复杂度 操作次数与输入规模 n 无关，固定次数 数组按索引取值、单变量赋值、栈/队列的入栈出栈 无增长，效率最高
O(log₂ⁿ) 对数复杂度 操作次数随 n 增长呈对数级增加（底数通常为2） 二分查找、二叉搜索树查找、平衡树操作 增长极慢，效率极高
O(n) 线性复杂度 操作次数与 n 成正比 数组遍历、链表遍历、线性查找 匀速增长，效率较高
O(n * log₂ⁿ) 线性对数复杂度 操作次数为 n 与 log₂ⁿ 的乘积 快速排序、归并排序、堆排序 增长较慢，高效排序算法通用复杂度
O(n²) 平方复杂度 操作次数与 n² 成正比 冒泡排序、插入排序、选择排序 增长较快，数据量大时效率低
O(n³) 立方复杂度 操作次数与 n³ 成正比 三重循环、矩阵乘法基础实现 增长快，仅适用于极小规模数据
O(2ⁿ) 指数复杂度 操作次数随 n 呈指数级增长 斐波那契数列递归实现、子集枚举 增长极快，数据量稍大即无法运行
O(n!) 阶乘复杂度 操作次数为 n 的阶乘 全排列枚举、旅行商问题暴力解法 增长最快，仅适用于极端小规模数据

提示： log₂n 是 对数，详见 链接

复杂度函数曲线

执行效率

复杂度越低，算法效率越高。

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₂ⁿ) 例子

二叉树

复杂度 O(2ⁿ) 例子

判断是否包含指定子序列

如：字符串 abc 有多少个子序列？

答：有以下个子序列

a
b
c
ab
ac
bc

总结：2³ - 2，渐进法表示：2ⁿ

最好、最坏、平均时间复杂度

  • 最好情况：算法在最优输入下的时间复杂度（如有序数组的冒泡排序，最好为 O(n)

  • 最坏情况：算法在最差输入下的时间复杂度（如逆序数组的冒泡排序，最坏为 O(n^2)

  • 平均情况：算法在所有可能输入下的期望时间复杂度，是更具实际参考价值的指标。

意义

算法设计中，优先选择 低时间复杂度 的方案

题

求解两个长度为n的序列 X 和 Y的一个 最长公共子序列（如序列 ABCBDAB 和 BDCABA 的一个最长公共子序列为 BCBA ）可以采用多种计算方法。如可以采用蛮力法，对X的每一个子序列，判断其是否也是Y的子序列，最后求出最长的即可，该方法的时间复杂度为（ ）

经分析发现该问题具有最优子结构，可以定义序列长度分别为 i 和 j 的两个序列 X 和 Y 的最长公共子序列的长度为 C[i]，如下式所示

采用 自底向上 的方法实现该算法，则时间复杂度为( )

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

原文出处：/show_1GWtjNqqtCm.html

吉ICP备15003043号