数据结构与算法-复杂度分析

我们都知道，设计数据结构和算法是为了让程序跑的更快、性能更好，同时能节省空间。所以算法的执行效率是一个非常重要的考量指标，一般这个指标我们可以通过分析时间复杂度和空间复杂度来衡量。

为什么需要复杂度分析

代码写完后在机器上执行一遍，我们就能知道算法执行的时间和占用的内存，为什么还要做复杂度分析呢？因为这种方式测算的结果有非常大的局限性。

测试结果依赖测试环境

直接执行代码统计的结果很大程度上依赖于测试所使用的环境。同样一段代码，在十年前破旧的电脑上执行和现在最新，配置最高的电脑上执行，时间肯定是不一样的。都是最新的电脑，Intel 和 AMD 的处理器跑出来的结果也可能不一样。这样，程序的性能就受到了环境的影响，并不能准确的反映出程序的好坏。

测试结果受数据规模的影响大

测试数据规模的不同，测试的结果相差很大。测试数据规模太小，测试结果可能无法真实地反应算法的性能。

所以，我们需要一个方法，不用具体的数据测试就可以粗略的判断算法的执行效率。

时间复杂度

算法的执行效率，简单的说，就是代码执行的时间。在不执行代码的情况下，通过计算每一行代码执行的次数来估计代码的执行时间，这里我们假设每行代码执行的时间是相同的。

举个例子，先看下面这段代码的执行次数。

int sum(int n) {
    sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
         	sum += i;   
        }
    }
}

第二行执行了一次，第三行执行了 n 次，第四行和第五行执行了 n 的平方次，所以这段代码执行了 $2n^2$+n+1 次，代码执行的总时间是与 n 成正比的，我们可以用一个公式来表示：

T(n)=O(f(n))=O(2n^2+n+1)

当 n 足够大时，后面的整数可以忽略不计，由于是粗略的估计，所以我们只取表达式中最大的量级来表示代码的时间复杂度。上面的公式可以简写成：

T(n)=O(n^2)

即我们可以说上面那段代码的时间复杂度为O(n^2)。

时间复杂度分析

只关注循环最多次数的代码

上面说了我们只取量级最大的代表时间复杂度。所以求算法的时间复杂度，最关键的就是计算出循环次数最多的那段代码执行的次数。

对于上面那段代码，我们只需要求出sum += i;这一行代码执行的次数，就可以计算出代码的时间复杂度。

加法原则

一个程序中有多个代码块时，总的复杂度等于量级最大的那段代码的复杂度，我们可以用公式表示：

T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

举个栗子，下面这段代码中的时间复杂度就是根据加法原则用最大量级的复杂度代表程序的复杂度。

int sum(int n) {
    int sum1 = 0;
    for (int i = 0; i < 100; i++) {
        sum1 += i;
    }
    
    int sum2 = 0;
    for (int i = 0; i < n; i++) {
        sum2 += i;
    }
    
    int sum3 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum3 += j;
        }
    }
    
    return sum1+sum2+sum3;
}

上面的代码中三个代码块的时间复杂度分别是常量时间，O(n) 和 O($n^2$) 。根据前面说的，当 n 足够大时，常量和 O(n) 可以忽略不计，所有这段代码的时间复杂度为 O($n^2$) 。

乘法原则

和加法原则类似，当代码中存在嵌套代码时，时间复杂度等于嵌套代码内外的复杂度乘积。用公式表示：

T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n))*O(g(n))

这里也举个栗子，

int sum(int n) {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        ret += add(i);
    }
    return ret;
}

int add(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += i;
    }
    return sum;
}