算法 -- 复杂度分析

算法是指通过操作数据来解决程序问题的一组方法，对于同一个问题，也许可以使用不同的算法来解决，但过程中消耗的资源和时间却会有很大的区别，这个时候我们就需要选择最高效的算法。而衡量一个算法是否高效，是从算法执行时所占用的「时间」和「空间」这两个维度去考量。

• 时间维度：是指执行当前算法所消耗的时间，通常用「时间复杂度」来描述。
• 空间维度：是指执行当前算法需要占用多少内存空间，通常用「空间复杂度」来描述。

在实际开发中，评价算法效率还是以「时间复杂度」为主的，因为现代计算机在垃圾回收和内存性能上的提升很迅速，基本不过多考虑空间复杂度了。

一、时间复杂度

时间复杂度描述的是执行当前算法所消耗的时间，但不表示算法实际执行所需要的真实时间。为什么呢？先来看个例子：

int sumFunc(int n) {

    int num = 0;                   //执行1次
    for (int i = 1; i <= n; ++i) { //执行n+1次

          num = num + i;           //执行n次
    }
    
    return num;
}

假设每行代码的执行时间为t，则执行此算法消耗的时间为：T = (2n + 2) * t。但实际上，程序执行非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且统计每行代码的执行时间也是没有必要的，就拿这个算法来说，当n无限大时，常量2对总时长来说也就没有意义了。

因此，时间复杂度不表示执行算法所消耗的实际时间，表示的是执行时间随数据规模增长的变化趋势。从上面的算法可以看出，执行时间T和n是成正比的，对于这个趋势，我们用「大O符号表示法」来表示算法的时间复杂度：

其中，T(n)表示代码执行时间，n表示数据规模的大小，f(n) 表示代码执行次数总和，O表示正比例关系。这个公式全称是：算法的渐进时间复杂度。

1. 大0时间复杂度计算法则

由于大O时间复杂度是用来表示算法的执行时间随数据规模增长的变化趋势，所以当n变得越来越大时，f(n)中的低阶、常量、系数三部分影响不了其增长趋势，可以直接忽略他们。因此计算法则为：

• 若执行次数总和是个常数，则用常数1代表：3 -> O(1)
• 只保留最高阶项：n^3 + 2n^2 + 5 -> O(n^3)
• 如果最高阶项的系数不为1，则忽略系数： 2n^3 -> 0(n^3)
• 如果最高阶为对数阶，忽略对数的底数：log2n - > O(logn)

2、常见的时间复杂度量级

复杂度量级	执行次数总和	时间复杂度
常数阶	12	O(1)
对数阶	5log2n + 20	O(logn)
线性阶	2n + 3	0(n)
线性对数阶	3nlog2n + 2n + 19	O(nlogn)
平方阶	3n^2 + 2n + 1	O(n^2)
立方阶	6n^3 +2n^2 + 3n + 4	O(n^3)
指数阶	2^n + n^2	0(2^n)
阶乘阶	3n! + 2^n + 1	O(n!)

上述各级的时间复杂度依次增大，算法的执行效率依次降低。根据大0时间复杂度计算法则，计算时只保留最高阶项。接下来根据代码实例来计算每级的时间复杂度，注意，指数阶和阶乘阶在实际中基本不存在，太耗时了，不用分析。

• 常数阶O(1)

//3 -> O(1)
void testSum1(int n){

    int sum = 0;                 //执行1次
    sum = (1+n)*n/2;             //执行1次
    printf("testSum1:%d\n",sum); //执行1次
}

//7 -> O(1)
void testSum2(int n){

    int sum = 0;                 //执行1次
    sum = (1+n)*n/2;             //执行1次
    sum = (1+n)*n/2;             //执行1次
    sum = (1+n)*n/2;             //执行1次
    sum = (1+n)*n/2;             //执行1次
    sum = (1+n)*n/2;             //执行1次
    printf("testSum2:%d\n",sum); //执行1次
}

连个算法的执行次数总和f(n)都为常数，所以时间复杂度均为O(1)。

• 对数阶O(logn)

//注：2^x =n,  x = log2n 

//2log2n + 2 -> O(logn)  
void testA(int n){
    
    int count = 1;            //执行1次
    while (count < n) {       //执行了log2n + 1次
        
        count = count * 2;    //执行了log2n次
    }
}

当while循环执行了x次后，若2^x>=n，就会跳出循环，所以while循环里的代码执行了x=log2n次。
f(n) = 2log2n + 2，最高阶为对数阶，时间复杂度为O(logn)。

• 线性阶O(n)

//2n+3 -> O(n)
void testSum3(int n){
    
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次

        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum); //执行1次
}

f(n) = 2n + 3 ，时间复杂度为O(n)。

• 线性对数阶O(nlogn)

//2nlog2n + 3n + 1 -> O(nlogn)
void testC(int n){
    
    for(int i=0; i<n; i++){       //执行了n+1次
        
        int count = 1;            //执行n次
        while (count < n) {       //执行了n*(log2n+1)次
            
            count = count * 2;    //执行了nlog2n次
        }
    }
}

f(n) = 2nlog2n + 3n + 1，最高阶为线性对数阶，时间复杂度为O(nlogn)。

• 平方阶O(n^2)

//3n^2+2n+3 -> 0(n^2)
void testSum5(int n){

    int i,j,x=0,sum = 0;           //执行1次
    for (i = 1; i <= n; i++) {     //执行n+1次

        for (j = 1; j <= n; j++) { //执行n*(n+1)

            x++;                   //执行n*n次
            sum = sum + x;         //执行n*n次
        }
    }
}

//n^2+2n+3 -> O(n^2)
void testSum4(int n){

    int sum = 0;                        //执行1次
    for(int i = 0; i < n;i++)           //执行n+1次

        for (int j = i; j < n; j++) {   //执行了(n+1)*n/2+1次

            sum += j;                   //执行了(n+1)*n/2 次
        }
    }
}

算法1中，f(n) = 3n^2 + 2n + 3，时间复杂度为O(n^2)。
算法2中，第二个循环里的执行次数为：n+(n-1)+(n-2)+...+1=(n+1)*n/2次，所以f(n) = n^2 + 2n + 3，时间复杂度为O(n^2)。

• 立方阶O(n^3)

//2n^3+2n^2+2n+2  -> O(n^3)
void testB(int n){

    int sum = 1;                          //执行1次
    for (int i = 0; i < n; i++) {         //执行n+1次

        for (int j = 0 ; j < n; j++) {    //执行n*(n+1)次

            for (int k = 0; k < n; k++) { //执行n*n*(n+1)次

                sum = sum * 2;            //执行n*n*n次
            }
        }
    }
}

f(n) = 2n³⁺²ⁿ2+2n+2，最高阶为立方阶，时间复杂度为O(n^3)。

二、空间复杂度

算法的实际占用存储空间包括：「程序本身所占空间」，「输入数据所占空间」，「辅助变量所占空间」。空间复杂度也不表示算法的实际占用空间，表示算法执行的存储空间与数据规模之间的增长关系：

实际计算的只是「辅助变量所占空间」，即在算法执行中临时占用的存储空间大小。空间复杂度比较常见的有：O(1)、O(n)、O(n²)。

• 常数阶O(1)

void testA(int n){
    
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    int temp;
    for(int i = 0; i < n/2 ; i++){
    
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }
}

这个方法将一维数组a中的n个数逆序存放在原数组中，过程中只申请了一个temp临时变量的存储空间，且这个辅助空间大小是个常量，不随n的值变化，所以空间复杂度O(1).

• 线性阶O(n)

void testB(int n){
    
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    int[] b = new int[n];
    for(int i = 0; i < n;i++){

        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){

        a[i] = b[i];
    }
}

这个方法也是将一维数组a中的n个数逆序存放在原数组中，过程中申请了一个空间大小为n的临时数组b，这个辅助空间大小是随n值变化的，所以空间复杂度为O(n)。

三、复杂度分析的四个概念

• 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
• 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
• 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
• 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

参考

算法的时间与空间复杂度（一看就懂）。