2022年4月学习记录 - 时间复杂度总结

2022-12-15 链接修复

  1. 链接修复：文章跳转链接修复

本文只是时间复杂度的简单介绍，学习做题请前往2022年9月学习记录 - 时间复杂度题目训练

时间复杂度

常见的时间复杂度

1.常数阶O(1)
2.对数阶O(log2n)
3.线性阶O(n)
4.线性对数阶O(nlog2n)
5.平方阶O(n2)
6.立方阶O(n3)
7.k次方阶O(nk)
8.指数阶O(2n)

最坏时间和平均时间

最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例,该算法的运行时间不可能大于O(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

计算方法

求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句：算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

具体实例

O(1)

常数阶，即时间复杂度不随着规模n的增大而增大。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数

1
2
3
4
5
6
7
8
9
10
int x=91; 
int y=100;
while(y>0) {
    if(x>100) {
        x=x-10;
        y--;
    } else {
    x++;
    }
}

T(n)=O(1)

这个程序看起来有点吓人，总共循环运行了1000次，但是这段程序并没有n，因此它只是一个常数阶的函数

O(n)

一次阶时间复杂度。耗费的时间与规模n成一阶线性关系。

1
2
3
4
5
int n;
cin >> n;
while (n--) {
    cout << n << endl;
}

O(n^3)

三阶线性关系。（n阶线性以此类推即可。）就好像矩阵相乘就永远是O（n^3 ）

1
2
3
4
5
6
7
8
9
10
int total = 0;
int n;
cin >> n;
for (int i = 0; i != n; i++) {
    for (int j = 0; j != i; j++) {
        for (int k = 0; j != j; k++) {
            total++;
        }
    }
}

内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句的执行次数：则该程序段的时间复杂度为

T(n)=O(n^3 /6+低次项)=O(n^3)

常见的算法时间复杂度由小到大

Ο(1)＜Ο(log2(n))＜Ο(n)＜Ο(nlog2(n))＜Ο(n^2) ＜Ο(n^3) ＜…＜Ο(2^n) ＜Ο(n!)

分析法则

在计算算法时间复杂度时有以下几个简单的程序分析法则:

1.对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

2.对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下”求和法则”

3.求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
3.对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

4.对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下”乘法法则”

乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))

5.对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:

(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))

(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

参考资料

[C++]时间复杂度&空间复杂度