如何判断一个算法的好坏

前言

小A和小B两人写了相同一个功能代码，而小A的代码老板运行后发现耗时为100ms，消耗内存10MB。而小B的代码老板运行以后，发现耗时为100S，消耗内存100MB。如果你是老板你会选则使用谁的代码。对于超过3秒即划走的用户而言，100s显然是不行的。小A和小B代码耗时与运行时占用内存的2种方式，是判断算法好坏的最重要的2种标准，分别为时间复杂度与空间复杂度。上面都是程序运行以后才知道耗时与占用内存，那么如何在没有运行程序时对算法进行提前预估呢？

关键代码执行次数

要预估时间复杂度，可以计算算法中关键代码的操作执行次数。

如下

情景一：

小明在绕操场匀速跑步2秒跑完1米，跑300米则需要600秒，如果跑步n米，则需要2 n 秒。则有

T(n) = 2n

情景二：

小明绕操场跑步，跑第1米需要1秒，跑第2米需要2秒，跑第3米需要3秒...跑n米需要n秒。

则小明跑n米的函数计算公式为

T(n) = 1 + 2 + 3+ 4 + ... + n = (1 + n)n/2 =0.5n + 0.5n^2

情景三

小明绕操场跑步，总路程40米，第1秒能跑27米，跑第2秒能跑9米，第3秒能跑3米，跑完最后一米需要多长时间。由对数运算公式可得，小明跑完40米的计算公式为

T(n) = log(3)(40)

若总路程为n 米，则有

T(n) = log(3)(n)

渐进时间复杂度

通过情景一二的计算，我们可以预估一个算法的时间复杂度，但因为当n取值不一样时，仍然不能判断到底哪一个更快，例如当n为1时，明显情景二更快一些。这时我们需要使用渐进时间复杂度进行分析，即大O表示法。

当n趋近于无限大时，有 T(n) / f(n) 的极限值有不为0的常数，则记作T(n) = O(f(n))。

情景一通过大O表示法则为：O(2n)，由于n趋近于无限大，忽略常数项，则记作O(n) 情景二通过大O表示法则为：O(0.5n + 0.5n^2 )，由于n趋近于无限大，忽略常数项保留最高阶项，记作O(n^2)。 情景三通过大O表示法则为：O(log(3)(n))，由于为了与幂次方做对比，则通过换底公式有，O(log(2)(n) / log(2)(3))，由于n趋近于无限大忽略除数，底数足够小省略底数不写，则有O(log n) 情景四幂函数，同样通过换底公式则有 O(2^x)

通过下图，我们分析出当n无限大时，常用的几个函数耗时从小到大为：

由于对数函数画图时没找到2为底在哪设置，hhhh

O(1) < O(log n) < O(n^2) < O(2^n)

空间复杂度

在程序运行指令中，需要存储一些中间数据所占用的内存空间即为空间复杂度，有 S(n) = O(f(n))。

如下函数，传入的n并不影响i所占用的空间，记作O(1)

f(n) {
  let i = 3n
}

如下函数，传入的n所占用总空间成正比，记作O(n)

f(n) {
  let array = new Array(n)
}

如下函数，传入的n与二位数组成正比，记作O(n^2)

f(n) {
  let array = new Array(n).fill(new Array(n))
}

取舍

计算机的运行速度和空间资源是有限的，时间复杂度与空间复杂度当然都越小越好。在绝大多数情况下时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的运行速度。

0人点赞

日记本