算法之空间复杂度和时间复杂度

时间复杂度:

用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。

例子:

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

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

对数阶O(log n)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

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

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

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

线性阶O(n)

语句①的频度为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(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是n*O(log n)了，于是记作O(nlog n)。

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

平方阶O(n²)

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

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

排序算法对比

空间复杂度

用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。

例子:

空间复杂度 O(1)

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

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

空间复杂度 O(n)

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

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

**参考文献： https://blog.csdn.net/zolalad/article/details/11848739

https://zhuanlan.zhihu.com/p/50479555**