数据结构与算法 1-4 常见时间复杂度与大小关系

本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

一

最常见的时间复杂度

上面表格中分为三列：

1. 执行次数函数举例。就是前几个小节分析的F(n)函数，F(n)是关于问题规模和执行总的基本操作数的函数；
2. 阶。就是时间复杂度T(n)。对应着就是F(n)去掉次要项以及常数项后的g(n)函数，此时称g(n)为F(n)的渐进函数，然后通过大O记法来表示时间复杂度T(n)，此时T(n) = O(g(n))；
3. 非正式术语。由于我们不关心基本操作数的细节，只关心数量级和趋势，因此虽然不同算法的F(n)可能不同，但是通过大O记法的时间复杂度总归是那么几种情况，因此相应的为这几种情况进行一个非正式的命名。

下面以执行基本操作总数3n^2 + 2n + 1，即F(n) = 3n^2 + 2n + 1为例，来详细说明一下计算时间复杂度的大致过程。其实要想求时间复杂度只需要记住上一小节提到的6个基本计算规则即可：

1. 基本操作，即只有常数项，认为其时间复杂度为O(1)
2. 顺序结构，时间复杂度按加法进行计算
3. 循环结构，时间复杂度按乘法进行计算
4. 分支结构，时间复杂度取最大值
5. 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
6. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

1-4是用于计算算法的总的基本操作说F(n)，5,6是求解时间复杂度相关的计算规则。

此时已知了基本操作总数F(n)，因此1-4条基本计算规则用不到了。3n^2 + 2n + 1按照5的计算规则，只关心基本操作数的最高次项，去掉其他次要项以及常数项，因为我们只关心数量级和趋势，可以看出3n^2 + 2n + 1的趋势是有n^2所主导的，所以把n作为次要项，然后去掉其余的常数项，最终得到的g(n) = n^2，时间复杂度T(n) = O(g(n)) = O(n^2)。

二

常见时间复杂度之间大小关系

根据上图可以看出这些常见时间复杂度的大小关系，需要记住下面的大小关系：

下面简单举几个例子，左边部分是O里面是算法执行的总的基本操作数，通过大O记法变成右边时间复杂度的形式。

1. O(5) ==> O(1)
2. O(2n + 1) ==> O(n)
3. O(n^2 + n + 1) ==> O(n^2)
4. O(3n^3 + 1) ==> O(n^3)

根据常见时间复杂度的大小关系可以得出上面4个时间复杂度所耗时间大小关系：O(n^3) > O(n^2) > O(n) > O(1)，也就是算法的效率。