如何衡量算法时间复杂度，空间复杂度以及大O表示法

算法是用来解决特定的问题的一种思想，对于同一个问题，可以有多种实现方式，最终的结果是一样的，但是整个过程需要的时间和资源不同，我们就需要在时间和空间上进行衡量。

概念

时间复杂度：当前算法所需要的运行时间

空间复杂度：当前算法所需要的内存空间

大 O 表示法：也叫做渐进式时间复杂度，公式为 $T(n)=O(f(n))$ 其中 f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。举个例子

大 O 符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

大 O 表示法的推导思路

1. 用常数 1 取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是 1，则去除与这个项相乘的常数。
4. 得到的最后结果就是大 O 表达式。

常数阶

let sum = 0,
  n = 100;
console.log("www.1024nav.com");
console.log("www.1024nav.com");

这段代码结合第一点，所有加法常数，所以是 $O(1)$

线性阶

一般含有非嵌套循环，线性阶就是随着问题规模 n 的扩大，对应计算次数呈直线增长。

let i,
  n = 100,
  sum = 0;
for (i = 0; i < n; i++) {
  sum = sum + i;
}

因为循环体中的代码需要执行 n 次，所以是 $O(n)$

平方阶

for (i = 0; i < 100; i++) {
  for (j = 0; j < 100; j++) {
    console.log("www.1024nav.com");
  }
}

外循环执行 100 次，内循环执行 100 次，所以是 n 的平方 $O(n^2)$，如果内循环再嵌套一层，则是 $O(n^3)$

对数阶

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

循环体里面每次都 *2，具体 n 的值就越来越近，这时可以计算 $2^i = n$，$i = log(2)n$，所以这段程序的时间复杂度是 $O(log n)$

时间复杂度总结

例子	时间复杂度	术语
1024nav	$O(1)$	常数阶
$2n + 1$	$O(n)$	线性阶
$n^2 + 3n + 5$	$O(n^2)$	平方阶
$3log(2)n + 1024$	$O(log n)$	对数阶
$2n + 3log(2)n + 1024$	$O(log n)$	nlogn 阶
$n^3 + 2n^2 + 3n + 1024$	$O(n^3)$	平方阶
$2^n + 1024$	$O(2^n)$	指数阶

空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量。

算法执行期间所需要的存储空间包括 3 个部分：

• 算法程序所占的空间；
• 输入的初始数据所占的存储空间；
• 算法执行过程中所需要的额外空间。
• 在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

算法的空间复杂度的计算公式记作：$S(n)=O(f(n))$，其中，n 为问题的规模，$f(n)$ 为语句关于 n 所占存储空间的函数。

空间复杂度总结

空间复杂度，就是通过空间换取时间的方式来解决问题。具体哪一种好，还是得具体问题具体分析。

如果您有什么看法或意见，欢迎通过右边的反馈悬浮框反馈

本文为原创，未经同意授权，禁止任何媒体或个人自媒体以及任何声明式转载

商业侵权必究，如需授权请联系340443366@qq.com

原文链接：https://www.1024nav.com/blog/algorithm-and-complexity

---