如何评价一个算法的好坏？-复杂度

如何评价一个算法的好坏？以下两个维度：

时间复杂度：估算程序指令的执行次数（执行时间）

空间复杂度：估算所需占用的存储空间

我们一般用大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

常见的复杂度：

*****  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年。

通过这一个例子，我们可以知道不同的算数有着很大的差距。有时候算法之间的差距，往往比硬件方面的差距还要大。

所以，对于咱们程序猿来说，咱们写的算法的优化方向是：

用尽量小的存储空间

用尽量少的执行步骤

在实际开发过程中，可以根据实际情况可以选择以空间换时间,或者以时间换空间。