什么是时间复杂度？时间复杂度有什么意义？

这篇文章回答两个问题：
什么是时间复杂度？时间复杂度有什么意义？

时间复杂度

维基百科上这样描述：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

简单来说，时间复杂度是一个用于研究算法而抽象出来的一个概念，用于评价一个算法最坏的情况时在时间层面的表现。

我们先来看一个冒泡排序：[C语言]

#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

我们来分析一下这个排序算法bubble_sort执行步骤：

1. 申明 i,j,temp;
2. 赋值 i = 0;
3. 判断 i < len - 1;
4. 赋值 j = 0;
5. 判断 j < len - 1;
6. 判断 arr[j] > arr[j + 1];（我们研究的是最坏的情况，所以假设这个判断每次都中）
7. 赋值 temp = arr[j];
8. 赋值 arr[j] = arr[j + 1];
9. 赋值 arr[j + 1] = temp;
10. 赋值 j++;
11. 重复4-9的步骤，直至4条件不成立
12. 赋值 i++;
13. 重复2-11的步骤，直至2条件不成立

假设每个执行任务的时间分别为：t0、t1、t2、t3....t9，
那么排序所需要的时间是
Time = t0 + (t1 + len * (t2 + t3 + len * (t4 + t5 + t6 + t7 + t8 + t9 )))
现在我们来假设三种情况

1. len 等于 0
   Time = t0 + t1 ;
2. len 等于 1
   Time = t0 + ... +t9;
3. len 等于 足够大的数，如1,000,000,000
   Time = ?

对于前面两种情况，运行速度的快慢取决于计算机硬件的性能，对于算法的研究意义不大，我们研究的是第三种情况，数据量足够大。

由
Time = t0 + (t1 + len * (t2 + t3 + len * (t4 + t5 + t6 + t7 + t8 + t9 )))
得到：
Time = t0 + t1 + (t2 + t3) * len + (t4 + t5 + t6 + t7 + t8 + t9) * len ^ 2

我们进一步用常数a、b、c 来代表上面的几个时间常数
Time = a + b*len + c * len^2

用一点极限的理论,当len趋近于无穷大时， 前面的a + b * len 可以忽略不计：
Time(len->无穷大) = c * len^2;

通常我们这个记作：T(n) = O(n ^ 2),即该算法的时间复杂度为O(n^2)，读作O(N平方)或指数时间。

再来看其他常见的时间复杂度例子：

• 常数时间 O(1)
  举例(简单赋值)： a = 1;
• 对数时间 O(log(n))
  举例（有序数组二分搜索）

    // while循环
int binary_search(const int arr[], int start, int end, int khey) {
    int mid;
    while (start <= end) {
        mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
        if (arr[mid] < khey)
            start = mid + 1;
        else if (arr[mid] > khey)
            end = mid - 1;
        else
            return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
    }
    return -1;
}

• 线性时间 O(n)
  举例(挨个匹配)：

    for(i = 1; i < n ; i ++) {
        if(arr[i] = target) return i;
    }

现在我们引出了什么是时间复杂度，那时间复杂度这个概念有什么意义呢？
我们知道，当n足够大时，有：
1 < log(n) < n < n^2
所以，时间复杂度的概念可以描述一个算法在最差的环境下需要什么级别的时间，时间复杂度可以帮助我们优化算法。
比如，做数组搜索，在最坏的情况并且n足够大时，有序数组的二分搜索(时间复杂度O(logn))会远比挨个匹配(时间复杂度O(n))快。
所以我们知道一个数组是有序数组时，我们做搜索应该选择二分搜索而不是挨个匹配。

如果你现在还不是很理解，那一定是我没有讲清楚。你可以继续阅读《算法导论》来更真切的理解时间复杂度的意义。
也可以来信讨论：lyc_chen@qq.com
参考：
维基百科-时间复杂度