算法的时间复杂度

1. 什么是时间复杂度

「时间复杂度是一个函数，它定性描述该算法的运行时间」。

我们在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的答题时间。

通常，我们会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

比如说：

//这个程序中，我们估算 doSomething() 这个操作的数量来代表程序消耗的时间
for(int i = 0;i < x; i++){
    for(int j = 0; j < y;j++){
        doSomething(); //这就是算法的操作单元
    }
}

用O(f(n))来记作时间复杂度，其中：

1. n是算法的问题规模 => 对应上面程序的 doSomething()
2. f(n)是操作单元数量 => 对应上面程序的 doSomething() 操作的次数

所以说，O(f(n)) 就是对 f(n) 消耗的时间的估算（这里的“估算”指的是”一般情况“）（对于大O是什么，下一节有详细讲解）

随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))。

2. 什么是大O

结论：算法的时间复杂度是多少指的都是一般情况。

=>

算法导论说：大O用来表示上界的，也就是算法最坏运行情况的时间上界。

但是：

插入排序的最坏情况是O(n^{2)，快速排序也是O(n}2)，但是，

众所周知，插入排序的时间复杂度为O(n^2)，快速排序的时间复杂度是O(nlogn)，

「但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界」。

我们主要关心的还是一般情况下的数据形式。

「面试中说道算法的时间复杂度是多少指的都是一般情况」。但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。

3. 不同数据规模的差异

如下图中可以看出不同算法的时间复杂度在不同数据输入规模下的差异。

1. 数据规模很大的时候，下式满足：

   O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

2. 为什么在计算时间复杂度的时候要忽略常数项系数：

   因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量

   例如上图中20就是那个点，n只要大于20 常数项系数已经不起决定性作用了。

3. 但是规模小时，可能不满足。

   所以说在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等）。

4. 还有一点要注意：要注意大常数，如果这个常数非常大，例如10^7 ，10^9 ，那么常数就是不得不考虑的因素了。

4. 复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：

O(2*n^2 + 10*n + 1000) 

那这里如何描述这个算法的时间复杂度呢？

1. 一种方法就是简化法。

   1. 去掉运行时间中的加法常数项 （因为常数项并不会因为n的增大而增加计算机的操作次数）。

      O(2*n^2 + 10*n)
      

   2. 去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）。

      O(n^2 + n)
      

   3. 只保留保留最高项，去掉数量级小一级的n （因为n^2 的数据规模远大于n），最终简化为：

      O(n^2)
      

2. 如果这一步理解有困难，那也可以做提取n的操作，变成O(n(n+1)) ，省略加法常数项后也就别变成了：

   O(n^2)
   

   所以最后我们说：这个算法的算法时间复杂度是O(n^2) 。

3. 也可以用另一种简化的思路，其实当n大于40的时候， 这个复杂度会恒小于O(3 * n^2)， O(2 * n^2 + 10 * n + 1000) < O(3 * n^{2)，所以说最后省略掉常数项系数最终时间复杂度也是O(n}2)。

5. O(logn)中的log是以什么为底？

平时说这个算法的时间复杂度是logn的，不一定是log 以2为底n的对数，可以是以10为底n的对数，也可以是以20为底n的对数。

「统一说 logn，也就是忽略底数的描述」

为什么可以这么做呢？如下图所示：

假如有两个算法的时间复杂度，分别是log以2为底n的对数和log以10为底n的对数，那么这里如果还记得高中数学的话，应该不能理解以2为底n的对数 = 以2为底10的对数 * 以10为底n的对数。

而以2为底10的对数是一个常数，在上文已经讲述了我们计算时间复杂度是忽略常数项系数的。

抽象一下就是在时间复杂度的计算过程中，log以i为底n的对数等于log 以j为底n的对数，所以忽略了i，直接说是logn。

这样就应该不难理解为什么忽略底数了。

6. 关于O(n) 、O(n^2) 和 O(nlogn) 具体的例子

// O(n)
void function1(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        k++;
    }
}

// O(n^2)
void function2(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            k++;
        }
    }

}

// O(nlogn)
void function3(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j < n; j = j * 2) { // 注意这里j=1
            k++;
        }
    }
}

关于测试三种算法的耗时，完整的测试代码如下：

#include 
#include 
#include 
using namespace std;
using namespace chrono;
// O(n)
void function1(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        k++;
    }
}

// O(n^2)
void function2(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            k++;
        }
    }

}
// O(nlogn)
void function3(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j < n; j = j * 2) { // 注意这里j=1
            k++;
        }
    }
}
int main() {
    long long n; // 数据规模
    while (1) {
        cout << "输入n：";
        cin >> n;
        milliseconds start_time = duration_cast(
            system_clock::now().time_since_epoch()
        );
        function1(n);
//        function2(n);
//        function3(n);
        milliseconds end_time = duration_cast(
            system_clock::now().time_since_epoch()
        );
        cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}

结果是：O(n) 的速度很快，而 O(n²) 的速度比前者慢了好多好多，但是，出于算法的复杂度，O(log(n) 的复杂度只比 O(n) 慢一个数量级，所以说，将 O(n²) 的算法的时间复杂度改为 O(log(n) 就是一种典型的、优秀的优化方式。

7. 一个分析的例子

通过这道面试题目，来分析一下时间复杂度。题目描述：找出n个字符串中相同的两个字符串（假设这里只有两个相同的字符串）。

如果是暴力枚举的话，时间复杂度是多少呢，是O(n^2)么？

这里一些同学会忽略了字符串比较的时间消耗，这里并不像int 型数字做比较那么简单，除了n^2 次的遍历次数外，字符串比较依然要消耗m次操作（m也就是字母串的长度），所以时间复杂度是O(m * n * n)。

接下来再想一下其他解题思路。

先排对n个字符串按字典序来排序，排序后n个字符串就是有序的，意味着两个相同的字符串就是挨在一起，然后在遍历一遍n个字符串，这样就找到两个相同的字符串了。

那看看这种算法的时间复杂度，快速排序时间复杂度为O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的操作，就是O(m * n * logn) 。

之后还要遍历一遍这n个字符串找出两个相同的字符串，别忘了遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m * n * logn + n * m)。

我们对O(m * n * logn + n * m) 进行简化操作，把m * n提取出来变成 O(m * n * (logn + 1))，再省略常数项最后的时间复杂度是 O(m * n * logn)。

最后很明显O(m * n * logn) 要优于O(m * n * n)！

所以先把字符串集合排序再遍历一遍找到两个相同字符串的方法要比直接暴力枚举的方式更快。

这就是我们通过分析两种算法的时间复杂度得来的。

「当然这不是这道题目的最优解，我仅仅是用这道题目来讲解一下时间复杂度」。

8. 总结

这篇文章讲了什么是时间复杂度，怎样表达时间复杂度，数据规模和时间复杂度的关系，最后用一个例子讲解一下时间复杂度。