什么是算法复杂度

算法（Algorithm）： 解决软件问题的一组步骤。从两个维度衡量算法的好坏：时间复杂度、空间复杂度。

• 时间复杂度：描述算法运行的时间。T(n) = O(f(n))它表示随着输入大小 n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。
• 空间复杂度：描述算法运行所需要的存储空间大小。S(n)=O(f(n)) 它表示随着输入大小 n 的增大，算法执行需要的空间可以用 f(n)来描述。

时间复杂度

T(n) 表示 算法表示输入大小为 n 时的运行次数函数。

假设存在一个变量C和函数f(n) ,当 n 趋向无穷大时：T(n)/f(n)=C。则可以记做：T(n)=O(f(n))。

f(n)描述随着n 增加算法执行时间需要的时间增长速度。

常见算法复杂度

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)

算法复杂度只是描述算法的增长趋势，并不能说一个算法一定比另外一个算法高效。这要添加上问题规模n的范围，在一定问题规范范围之前某一算法比另外一算法高效，而过了一个阈值之后，情况可能就相反了。

如何推导时间复杂度

算法复杂度推算分为三步：

1. 找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。
2. 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。
3. 用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

使用大O表示发通常有三种原则：

1. 用常数1取代运行时间中的所有加法常数；
2. 只保留时间函数中的最高阶项；
3. 如果最高阶项存在，则省去最高阶项前面的系数；

时间复杂度实例

O(1)

int i = 1;
int j = 2;
int k = 1 + 2;

👆代码，没有嵌套和循环语句，单个语句的频度均为1，不会随着问题规模n的变化而变化。因此，算法时间复杂度为常数阶，记作T(n)=O(1)。这里我们需要注意的是，即便上述代码有成千上万行，只要执行算法的时间不会随着问题规模n的增长而增长，那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。

O(logn)

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

👆代码，语句①频率时1，可以忽略。

语句②我们可以看到它是以2的倍数来逼近n，每次都乘以2。如果用公式表示就是1222…2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn。也就是说上述循环在执行logn次之后，便结束了，因此上述代码的时间复杂度为O(log n)。

其实上面代码的时间复杂度公式如果精确的来讲应该是：T(n) = 1 + O(log n)，但我们上面已经讲到对应的原则，“只保留时间函数中的最高阶项”，因此记作O(log n)。

O(n)

int j = 0; // ①
for (int i = 0; i < n; i++) { // ②
   j = i; // ③
   j++; // ④
}

上述代码中，语句①的频度为1，②的频度为n，③的频度为n-1，④的频度为n-1，因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1)来表示。进而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次幂和系数即O(n)=n，因此T(n)=O(n)。

在上述代码中for循环中的代码会执行n遍，因此它消耗的时间是随着n的变化而成线性变化的，因此这类算法都可以用O(n)来表示时间复杂度。

O(nlogN)

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

线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是n*O(log n)了，于是记作O(nlog n)。

O(n²)

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

平方阶可对照线性阶来进行理解，我们知道线性阶是一层for循环，记作O(n)，此时等于又嵌套了一层for循环，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。

排序算法 复杂度

空间复杂度

空间复杂度表示程序执行中对数据进行操作的工作单元和辅助存储空间。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。

空间复杂度实例

O(1)

int i = 1;
int j = 2;
int k = 1 + 2;

上述代码中临时空间并不会随着n的变化而变化，因此空间复杂度为O(1)。总结一下就是：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)，即 S(n) = O(1)。

O(n)

int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
   j = i;
   j++;
}

上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)。

总结

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

Ref

https://www.jianshu.com/p/f4cca5ce055a

https://cloud.tencent.com/developer/article/1769988

https://juejin.cn/post/6844904167824162823