算法笔记 1：时间复杂度/空间复杂度

一、概念

1.时间复杂度

这个与耗时并无直接联系。时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。简而言之，就是计算机执行一个算法快慢的量度体现。

2.空间复杂度

Space Complexity
解决一个实际问题可能有多种算法来实现，但是运行时候所占用的内存可能是不同的，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度体现。

二、表示

1.时间复杂度

我们一般用“大O符号表示法”来表示时间复杂度：T(n) = O(f(n))
n是影响复杂度变化的因子，f(n)是复杂度具体的算法。

常见的时间复杂度量级

常数阶O(1)
线性阶O(n)
对数阶O(log ₂n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(log ₂n) <O (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

2.空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义，一般也作为问题规模n的函数，以数量级形式给出。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)，

三、复杂度计算

1.时间复杂度

求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。
⑶ 用大Ο记号表示算法的时间性能。将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环。

时间复杂度为:O(1)

    private int getSum(int a) {
    int sum = 0;
     sum=sum+a;
    return sum;
}

时间复杂度用来表示代码执行时间的增长变化趋势的。上面的算法并没有随着变量的增长而增长耗费时间，那么无论这类代码有多长，都可以用O(1)来表示它的时间复杂度。
时间复杂度为:O(n)

 int i=0;
 while (i < n && arr[i]!=1){
    i++;
}

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。但是如果arr[i]等于1的话，则循环执行一次判断跳出，时间复杂度是O(1)。
时间复杂度为:O(log ₂n)

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

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

时间复杂度为:O(nlogN)

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

线性对数阶O(nlogN) 将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

时间复杂度为:O(n²)
如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

  for(x=1; i<=m; x++){
     for(i=1; i<=n; i++) {
       //
    }
}

它的时间复杂度为 O(m*n)，如果m=n,Tn=O(n²),

时间复杂度为:O(n³)
O(n³)相当于三层n循环，其它的类似还有K次方阶O(n^k)。

2.空间复杂度

算法所占用的存储空间主要包括：
1程序本身所占用的空间
2输入输出变量所占用的空间
3动态分配的临时空间，通常指辅助变量
输入数据所占空间只取决于问题本身，和算法无关。我们所说的空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，即第三项。通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
举个🌰：

 private void test1(int n) {
    int a = 0, b = 0, c = 0;
    int cnt;
    for (cnt = 0; cnt < n; cnt++) {
        a += cnt;
        b += a;
        c += b;
    }
}

空间复杂度为O(1)，因为只有a, b, c, cnt四个临时变量。且临时变量个数和输入数据规模无关。

第二个🌰：

 private int test1(int n) {
    int a = 0;
    if (n == 0) {
        return 1;
    }
    n -= a;
    return test1(n);
}

S(n) = O(n).空间复杂度为O(n)，因为每次递归都会创建一个新的临时变量a并且共递归执行n次。

四、其他

0.算法复杂度通常指什么？
算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源,简而言之也就是时间复杂度和空间复杂度的统称，一般求“复杂度”时，通常指的是时间复杂度。
1.为什么需要复杂度分析？
数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标，那就要进行时间、空间复杂度分析。
2.算法复杂度中的O(logN)底数是多少？
from: 知乎
若算法的 T(n) = O(log n)，则称其具有对数时间。由于计算机使用二进制的记数系统，对数常常以10为底（即log10 n，有时写作 lg n）。然而，由对数的换底公式，loga n和 logb n只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作O(log n)，而不论对数的底是多少，是对数时间算法的标准记法。

---

我的理解是首先要明白的是时间复杂度是为了表明一种趋势， 不过无论底数是什么,log级别的渐进意义是一样的，log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。如果采用二分法,那么就会以2为底数,三分法就会以3为底数,其他亦然。
3.时间复杂度和空间复杂度的关系？
没有直接关系。首先时间复杂度并不等效于程序执行速度，其次编程里的大部分空间换时间其实并没有改善时间复杂度。