如何评价一个算法的好坏？以下两个维度：
时间复杂度：估算程序指令的执行次数（执行时间）
空间复杂度：估算所需占用的存储空间
我们一般用大O表示法来描述复杂度。
一般地，我们需要忽略常数、系数和低阶
2022 >> O(1)
3n+4 >> O(n)
n^2+2n+3 >> O(n^2)
4n^3+3n^2+2n+1 >> O(n^3)
特殊地，log2(n) = log2(9) * log9(n)
所以一般把log2(n) 、 log9(n) 统称为logn
常见的复杂度：
| 12 | O(1) | 常数阶 |
| 2n + 3 | O(n) | 线性阶 |
| 4n^2 + 2n + 6 | O(n^2) | 平方阶 |
| 4log2n + 25 | O(logn) | 对数阶 |
| 3n + 2nlog3n + 15 | O(nlogn) | nlogn阶 |
| 4n^3 + 3n2 + 22n + 100 | O(n^3) | 立方阶 |
| 2^n | O(2n) | 指数阶 |
***** O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
复杂度大小对比如下：
下面举一个特别直观的例子，可以看到不同的算法的差别有多么大！！！！
大家肯定都知道斐波那契数列，它的递归写法如下：
public static int fib1(int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}它的迭代写法如下：
public static int fib2(int n) {
if (n <= 1) return n;
int a = 0;
int b = 1;
for (int i = 0; i < n - 1; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}递归写法，通过简单的归纳推理可以知道，递归写法的时间复杂度为O(2^n),迭代写法的时间复杂度为O(n).
假如我的电脑主频为1GHz（实际为2.9，这里为了方便计算），那么电脑的运算速度为10^9次/秒，那么现在我们分别用着两种算法算一下第64个斐波那契数（n=64）。
O(n)大约耗时6.4*10^(-8)秒。
O(2^n)大约耗时584.94年。
通过这一个例子，我们可以知道不同的算数有着很大的差距。有时候算法之间的差距，往往比硬件方面的差距还要大。
所以，对于咱们程序猿来说，咱们写的算法的优化方向是：
用尽量小的存储空间
用尽量少的执行步骤
在实际开发过程中，可以根据实际情况可以选择以空间换时间,或者以时间换空间。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/94490.html
