时间复杂度分析，这个很多人都不知道，更别谈会了！

时间复杂度

请原谅我也是一个标题党！

关于时间复杂度和空间复杂度分析的文章其实不少，但大多数都充斥着复杂的数学计算，让很多读者感到困惑，我就不跟大家扯皮了，关于什么是渐近分析、最坏时间复杂度、平均时间复杂度和最好的时间复杂度，以及大 记法等等，大家好好花点儿时间看看严老师的书就会了。

我们从代码和实现的层面讲讲，如何计算你写的代码的时间复杂度？

任何一门语言的逻辑结构无非三种：顺序结构、循环结构和分支结构，但是真正影响到时间复杂度只有循环结构，如果分支结构影响复杂度，也是因为分支内部包含了循环。

循环的实现有 for 和 while 两种形式，但是本质都是一样的，我们接下来均以 for 循环进行说明。

如果一个函数（语句）不包含循环、迭代或非常数时间的函数，则可以认为函数为 的时间。

// 非循环或者递归语句或函数
int love = 520;

比如交换两个数的 swap() 函数的时间复杂度就是 :

void swap(int *xp, int *yp) {     int temp = *xp;     *xp = *yp;     *yp = temp; }

一个循环如果仅仅运行常数次，那么时间复杂度也可以当作 来处理：

// c 表示一个常量
for(int i = 0; i < c; i++) {
    // O(1) 表达式
}

如果循环控制变量 i 递增/递减的步长为一个常数 ，则认为循环的时间复杂度为 。例如，以下函数的时间复杂度为 ：

// c 是一个正整数常量for(int i = 0; i < n; i += c) {    // O(1) 表达式}-------------------------------for(int i = n; i > 0; i -= c) { // O(1) 表达式}

，嵌套循环的时间复杂度等于最内层语句的执行次数。例如，下面示例循环的时间复杂度为 ：

for (int i = 1; i <= n; i += c) {
    for (int j = 1; j <= n; j += c) {
  // O(1) 表达式
    }
}

for (int i = n; i > 0; i -= c) {
    for (int j = i+1; j <= n; j += c) {
  // O(1) 表达式
    }
}

如果循环控制变量 i 乘以或除以一个常数 ，则循环的时间复杂度为 量级：

// c 是一个正整数常量for(int i = 1; i < n; i *= c) {    // O(1) 表达式}-------------------------------for(int i = n; i > 0; i /= c) { // O(1) 表达式}

简单地分析一下，循环控制变量到达 的顺序为  ，如果我们令 ，那么  ，也就是循环到达 n 仅仅会执行 次，复杂度自然为 量级。

比如二分查找（binary search）的迭代实现的时间复杂度就是 ：

int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
        if (arr[m] == x) 
            return m;

if (arr[m] < x) 
            l = m + 1; 
        else
            r = m - 1; 
    } 
    return -1; 
} 

如果循环控制变量 i 以指数级别增加或者减少，则时间复杂度为 量级。

情况一：

for(int i = 2; i <= n; i = pow(i, k)) {    // O(1) 表达式或语句}

这种情况下，i 的取值为 ，而最后一项一定小于等于 ，即   ，也就是说循环执行了 次，每一次迭代的时间为常数时间，则上面的迭代总的时间复杂度为 量级。

情况二：

// fun(i) 表示为 i 开方或者开立方
for(int i = n; i > 0; i = fun(i)){
    // O(1) 表达式或语句
}

i 的取值为，  ，所以迭代总共执行 次，时间复杂度为   量级。

如果程序中包含多个循环，又该如何时间复杂性？

如果程序中存在多个连续循环时，时间复杂度为多个单循环的时间复杂度之和。

for (int i = 1; i <= m; i += c) {      // O(1) 表达式或语句}for (int i = 1; i <= n; i += c) {    // O(1) 表达式或语句}

上面程序的时间复杂度为 ，当 时，则 ，依旧是 量级。

如果循环内部包含大量的 if...else... 语句时，又该如何计算时间复杂度？

在最好、平均和最差时间复杂度中，我们一般只关注最坏时间复杂度。考虑最坏的情况，当if...else... 条件中的语句导致执行时间复杂度的增加，就需要将其计算到最坏时间复杂度中。

int search(int arr[], int n, int x) 
{ 
    int i; 
    for (i = 0; i < n; i++) { 
        if (arr[i] == x) 
            return i; 
    } 
    return -1; 
} 

例如，考虑上面的线性搜索函数，其中我们考虑元素出现在数组 arr[] 的末尾或根本不存在的情况，分别对应 和 的时间复杂度，但是我们仅关注最坏的时间复杂度 。

当代码太复杂而无法考虑所有 if...else 情况时，我们可以忽略 if...else 和其他复杂的控制语句来计算最坏情况下的时间复杂度。

递归算法的时间复杂度又该如何计算？

很多算法都是基于递归思想的，我们分析这些递归算法，可以得到关于时间复杂度的递归关系式。比如 「归并排序」 的时间复杂度一般表示为 ，还有二分查找，汉诺塔问题等等，但是关于递归的时间复杂度并不简单。

对于递归的时间复杂度的计算主要有三种方式：

一、代入法：先对解进行猜想，然后用数学归纳法证明猜想的正确性。

已知   ，注意 前面的系数   ；

又很容易得到  和 之间的关系式，即  .

将 与 之间的关系式带入 当中，就是将所有的 替换为 ：

则， ，注意

就得到了 与 之间的关系式，

同理，  与 之间的关系为： ,

带入 ，得到 和 之间的关系式；

，注意

以此类推...

可以推知 与 之间的关系：

∴ 归并排序的时间复杂度为 量级。

二、主定理

令 和 1' data-formula-type='inline-equation'> 是常数， 是一个函数， 是定义在非负整数上的递归式：

其中我们将 解释为 或 ，那么 有如下渐近界：

  1. 若对某个常数 0' data-formula-type='inline-equation'> 有 ，则 .
  2. 若 ，则   .
  3. 若对某个常数 0' data-formula-type='inline-equation'> 有   ，且对某个常数 和所有足够大的 有 ，则   .

主定理对递归式 所提供的一种 “菜谱式” 的求解方法，关于主定理的证明就不在这里解释了，感兴趣可以看一下 《算法导论》4.6 节的主定理的证明。

我们这里直接 “下菜“ 即可。

已知   ；

首先和 对应起来

、 、

则

∴ .

即归并排序的时间复杂度为 .

三、递归树

在该方法中，我们绘制了一棵递归树，并计算了树的每一层所花费的时间。最后，我们总结了各级所做的工作。为了绘制递归树，我们从给定的递归开始，不断绘制，直到在级别之间找到一个模式。通常是算术或几何级数。

以递归关系 为例，其递归树可以表示为：

我们进一步打开表达式 ，以及表达式 :

继续把 ， 拆分。

而为了计算 ，则需要一层一层地将树中的所有结点累加起来，即：

上面序列的几何级数的系数为 5/16，为了获得上限，我们可以无限趋近于无穷大，获得 ，时间复杂度为 量级。

是不是被这种方法搞得晕晕乎乎，没关系，这属于了解内容，当然想深究的可以看看算法导论。

你该不会到这里就结束了吧！

其实计算算法的时间复杂度还有一种方法，就是根据题型去判断计算：

题型 时间复杂度
数组、动态规划 for 循环执行次数
链表 while 循环执行次数
栈、队列 栈或者队列的大小
二叉树 结点个数
回溯法、BFS/DFS 元素个数 O(n)
二分查找 log(n)
分治法 log n （归并排序、快速排序）

当然这也只是一个比较粗略的概括，时间复杂度的分析无定法，仅仅是大家的一个共识而已，最好的方法是，将你的代码结合数据跑起来，计算它的运行时间，但是这也需要大家规定设备的型号和运行内存等等硬件。

谁说深究不是一种品质呢？如果你真的对时间复杂度和空间复杂度感兴趣，那就研究下去！！！

赞 (0)

相关推荐