一学一记：代码时间/空间复杂度

¶一学一记：代码时间/空间复杂度

¶代码的复杂度分析

时间复杂度:

概念解释：代码的执行时间复杂表示的是一段代码的执行时间随数据规模增长的变化趋势**(它并不是表示具体的代码时间)，也叫做**渐进式时间复杂度
分析时间复杂度方法：
- 只关注循环最多的代码 ：一段代码的最大时间复杂度会由运行时间最长—也即时间复杂度最大的那段代码决定，因此分析一段代码的时间可以只关注的
  循环最多的那段代码的时间复杂度
- 加法法则 ： 总复杂度等于量级最大的那段代码的时间复杂度：类似于木桶效应，一段代码的总时间复杂度是内部多段代码执行时间复杂度之和，但是最能够代表复杂度趋势的还是量级最大的那段代码的执行时间复杂度
- 乘法法则：嵌套代码的时间复杂度等于内外代码复杂度的乘积 : 嵌套循环了 n*n 的代码总时间复杂度就是O(n^2)

常见时间复杂度量级:

多项式量级 : 常量阶 O(1) , 对数阶 O(logn) , 线性阶 O(n) , 线性对数阶 O(nlogn) , 次方阶 O(n^k)
非多项式量级: 指数阶 O(2^n) , 阶乘阶 O(n!) , 此类时间复杂问题称为NP(Non-Deterministic Polynomial ，非确定多项式)问题
扩展知识
- 多项式 : TODO

分析:

常数阶 O(1) : 一段代码中，不存在循环的，递归的情况下，代码的执行次数都是常数级别的，是根据数据规模可知的

对数阶级 O(logn) :
$$
数学概念 : 当存在 N=a^x , x 为以 a 为底的N的对数，记作 x = logaN
$$
由上述概念可知，如果代码的执行次数N和变量x存在以常数a为条件的指数关系-- N = a^x ，那么 x = logaN , 对数表示为 logaN , 对数阶量级的时间复杂度，忽略常数a，表示为 O(logn)

 i = 1;
while(i<n){
    i=i*2;
}
//第3行代码的时间复杂度就是这段代码的时间复杂度
//而它的执行次数受 n 取值的影响 ， i = 2^1 , i = x^2 .....i =2^n 
// 因此计算出对数函数表示为 log2N , 时间复杂度表示为 O(logn)

线性阶 O(n) : 一次函数概念
线性对数阶 O(nlogn) : 结合线性阶和对数阶，可以理解当 O(logn) 复杂度的代码循环了n次，总的时间复杂度就是 O(nlogn)
其他:
- O(m+n) ：之前有提到，一段代码总的时间复杂度是由规模较大的那个数决定的，当结果受到两个规模不定的数据影响时，时间复杂度就是O(m+n)
- O(m*n) ：与乘法法则一样，只是从 n 的互乘变成了 m,n 的互乘

空间复杂度:
- 概念解释 : 表示算法的存储空间与数据规模增长之间的关系，也叫做渐进式空间复杂度
- 常见空间复杂度 : O(1) , O(logn), O(n) , O(nlogn),O(n^2)

最好，最坏，平均，均摊时间复杂度分析

我们知道代码的时间复杂度受到会受到数据规模的影响，因此存在了，在不同情况下(数据规模或变量)，一段代码的时间复杂度是不确定的，从一个例子分析
1
2
3
4
5
6
7
8
9
10
11
int find(int[] array,int n,intx){
int i=0;
int pos = -1;
for(;i<n;i++){
if(array[i] == x){
pos = i;
break;
}
}
return pos;
}
这是从数组中查找某个输入 x 的代码，可以看出，当x分别处于数组头部，数组尾部和不在数组中时，对应的时间复杂度是不一样的，可以计算出对应的时间复杂度:
最好时间复杂度: O(1) , 最坏时间复杂度: O(n)
还有平均复杂度的概念，根据 x 可能出现在数组中的位置，再加上x不存在于数组中，一共有n+1种情况；而对应每种情况需要遍历的元素数量为
1+2+3…+n + n = n(n+3)/2 , 得出平均时间复杂度为 :
$$
(n(n+3)/2)/(n+1) = n(n+3)/2(n+1)
$$
在大O标记法中可以忽略掉常量，因此得到的平均复杂度为O(n)。这种方式得出来的平均时间复杂度，并没有计算x出现在数组位置 i 的概率,因此重新计算:
假设 x 出现在位置 i 的概率为 1/n ,x 出现在数组中的概率为 1/2 ，即 x 出现在数组位置 i 的概率为 1/2n ,得出新的平均时间复杂度为:
$$
11/2n + 22/2n + … + n*1/2n + n * 2/1 = (3n+1)/4
$$
这也是概率论中的加权平均值，还是忽略掉常量系数，平均时间复杂度为 O(n) .

均摊时间复杂度:

概念上可能和平均时间复杂度相近，使用场景比较特殊，暂时以 有规律的复杂度交替 来指代它的场景:

//代码来自极客时间《算法与数据结构之美04-王争》
// array表示一个长度为n的数组 
// 代码中的array.length就等于n 
int[] array = new int[n]; 
int count = 0; 
void insert(int val) { 
    if (count == array.length) { 
        int sum = 0; 
     	for (int i = 0; i < array.length; ++i){ 
            sum = sum + array[i]; 
        } 
        array[0] = sum; 
        count = 1; 
    } 
    array[count] = val; 
    ++count; 
}

要计算上面这段代码的时间复杂度，重点在 9，10，12 行，这是一个往数组中插入数据的方法，当数组被填满时，对数组进行一次O(n)的遍历求和(10行)，然后赋值到数组中的空余位置(12行)。也就是说，这段代码是每一次的 O(n) 复杂度操作之后，都会跟随着 n -1(这里指的是13行count =1之后的插入情况) 次O(1) 复杂度的操作。以平均时间复杂度分析的方式计算：
- 数据可插入的情况是 n +1 种情况 ( 数组有空余 + 数组需要遍历求和 )；
- 当数组中存在空余位置，插入操作是一次，否则进行一次 n 遍历，每种情况发生的概率都是 1/(n+1) ，
- 因此得到平均时间复杂度 :
- $$
  11/n+1 + 11/n+1 + … + n*1/n+1 = O(1)
  $$
整个的计算过程比较麻烦，针对这种特殊的分析场景，引入了摊还分析法的概念，将一次O(n) 复杂度的操作均摊到 n-1 次O(1) 的操作上(将它们每次循环看作一个整体)，n/(n-1) 均摊下来就是 O(1) 的常数阶。

小结 :
- 时间复杂度：表示的是代码执行时间随着数据规模变化的趋势，因此也称作 渐进时间复杂度，渐进函数用O(f(n))表示
- 复杂度分析：有几个需要关注的特征
  - 执行次数最多的代码：一段代码的时间复杂度由它的那段执行时间最长的代码决定，取最大值作为整段代码的时间复杂度表示
  - 嵌套代码：嵌套代码的时间复杂度等于内外嵌套代码时间复杂度的乘积，也叫乘法法则
  - O(m+n): 在可以确定一个最大规模数据量级的时候，关注其中一段代码的时间复杂度就可以，但是当存在两个以上数据规模不确定的情况时，整段代码的时间复杂度就等于多段代码的时间复杂度之和
  - 时间复杂度表示：最终的结果都会忽视常数，常数系数，常见的时间复杂度有:
    - 多项式量级:
      - O(1) : 常数阶
      - O(n):线性阶
      - O(logn):对数阶
      - O(nlogn):线性对数阶,即复杂度为O(logn)的代码循环了n次
      - O(n^x):次方阶
    - 非多项式量级:
      - O(2^n) : 指数阶
      - O(n!) : 阶乘阶
- 最好，最坏，平均时间复杂度，均摊时间复杂度:
  - 因为一段代码在不同的数据规模下，执行的时间复杂度不同，因此会因为数据分布的不同，产生最好,最坏，平均时间复杂度的概念
  - 最好时间复杂度：数据分布的情况符合代码执行的目的，例如一次遍历就查找到目标，复杂度就是O(1)
  - 最坏时间复杂度: 数据分布与查找目的相反，需要进行所有情况的一次遍历，在单次循环查找中就是O(n)
  - 平均时间复杂度：因为最好，最坏的时间复杂度出现在极端的情况下，因此大部分情况只需要考虑代码的平均时间复杂度。代码的平均时间复杂度在不引入概率的情况下等于:
    - 需要遍历的次数 n , 数据在数据集中分布的情况m , n/m 就是平均时间复杂度
    引入数据分布在数据集中的概率:
    - 数据分布在每个位置的概率 1/n , 数据集长度n，11/n + 21/n + … + n1/n + n1/2 = 平均时间复杂度
  - 均摊时间复杂度：在特定情况下适用的复杂度分析，当一次 O(n) 复杂度的操作之后跟随着 n 次 O(1) 级别的时间复杂度，可以将O(n) 级别的时间复杂度均摊到 n 次O(1) 的操作上