算法-复杂度分析

问题一：为什么要做算法的复杂度分析。
算法的本质就是一个快与省的问题，如何用最快的速度和最小的内存空间出处理某件事情，就是算法所要做的事情。那么判断算法的优劣程度也是依据于这些指标。提到算法必然会避免不了时间复杂度和空间复杂的分析。可以说复杂度分析就是整个算法学习的精髓，掌握了它。基本上数据结构和算法就掌握了一半。

到这里基本上可以回答上面的问题，但依然有疑惑。在编程环境中有很多东西可以进行算法效率的统计。但这是事后统计法这种方法有一定局限性。
一、测试结果非常依赖测试环境。
不错的硬件性能对于测试结果有很大的影响，如相同的代码i5的处理器，就比i3的处理器的速度要快。
二、测试结果受数据规模的影响很大。
相同的代码不同的数据规模，和数据结构测试的结果也有很大的差别。小规模的数据，对于算法来说根本就体现不出来算法的性能差异。

所以，需要一个不需要具体的测试环境的测试数据来测试，就可以粗略地估计算法的执行效率的方法。

大O复杂度表示法
算法的执行效率大体就是算法的执行时间，但如何在不运行程序的情况，看到程序的执行时间呢？
下面的代码,求1，2，3....n的累加之和，看看它的执行时间。

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

这段代码在电脑的CPU中的执行都是类似的操作：读取数据-运算-写数据（尽管CPU的执行个数与时间都不一样，但是可以忽略不记，因为这里只是粗略的估计），假设每行代码的执行时间为unit_time。在此基础上，这段代码的执行时间是多少？
在这段代码中每一行代码的执行都需要一个unit_time,而for循环里面的代码是执行了n遍。所以就需要2n* unit_time 的执行时间，那么这段代码的执行时间就是(2n+2)x unit_time。得出结论：所有代码的执行时间T(n)与每行代码的执行次数成正比。

T(n) = O(f(n))

对于上面的公式进行解释，T(n)表示的是执行时间,n为数据规模f(n)每行代码执行次数的总和。O表示的是执行是时间T(n)与f(n)成正比。大O时间复杂度并不是程序真正的执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，也称作渐进式时间复杂度，简称时间复杂度。
有了表示方法，那么如何做复杂度分析？
三个方法：
1.只关注循环次数最多的一段代码
大O表示法只是表示一种变化趋势，通常情况下我来都会忽略公式中的长量、低阶和系数。只需要记录一个最大阶量级，在分析一个算法，一段代码的时间复杂度，也仅仅只需要关注执行次数最多的那行代码即可。
2.加法法则：总复杂度等于量级最大的那段代码的复杂度

int cal(int n){
     int sum_1 = 0;
     int p = 1;
     for(;p<100;++p){
        sum_1 = sum_1 + p
    }
    int sum_2 = 0;
    int q = 1;
    for (;q<n;++q){
        sum_2 = sum_2 + q;
    }
    int sum_3 = 0;
    int i = 1;
    int j = 1;
    for (;i <= n;++i){
        j = 1;
        for (; j<= n;++j){
               sum_3 = sum_3 + i *j;
          }
    }
     return sum_1 + sum_2 + sum_3;
}

这段代码主要分成个部分sum_1 ~ sum_3,先逐个分析其时间复杂度，然后整合取以一个量级最大的那段代码作为整段代码的复杂度。
我们先来看看第一部分，从中我们可以看到这部分执行100次，这是一个常量级的复杂度，跟n的规模无关。注：常量级复杂度可以忽略。
我们继续看第二部分的代码，可以看出它的时间复杂度为O(n)。
继续，第三部分的代码的时间复杂度是O(n²),最大的量级的时间复杂度是O(n²),所以：总的时间复杂度就等于量级最大那段代码的复杂度
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码的乘积。

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

单独看cal()函数，我们假设f()只是做一次普通操作，那么它的时间复杂度就是O(n),但是f()函数本身就是一个时间复杂度为O(n)的函数，所以整个函数的时间复杂度 T(n) = T1(n)T2(n) = O(n*n) = O(n²).
几种常见的时间复杂度实例分析

图片来源《极客时间》
这里给出的时间复杂度基本上可以覆盖大部分的代码的时间复杂度分析，我们大概可以分为两类, 多项式量级 和 非多项式量级，其中非多项式只有两个O(2ⁿ)和O(n!).
当数据规模增大时，非多项式量级的执行时间会急剧增加，求解问题的执行时间会无限增长，非多项式时间复杂度是一种非常低效的算法。
我们主要分析的多项式的时间复杂度。
O(1) 常量级时间复杂度 一般情况下，只要算法中不存在循环语句，递归语句，无论的它的代码量有多大，其时间复杂度都只是O(1)

int i = 8;
int j = 6;
int sum = i + j;

O(logn)、O(nlongn) 对阶数时间复杂度，最常见也是最难分析的一种时间复杂度。

i = 1;
while (i <= n){
      i = i * 2;
}

从代码中我们可以看出第三行的重复次数是最多的