算法(algorithm)是由定义清晰的计算步骤所组成的操作序列。一旦我们确认了某个算法的正确性，接下来极其重要的一步就是分析它的运行时间和需要使用的空间资源。

数学基础

常用的四个关于相对增长率的定义

  • 大O标记：如果存在正常数C和\(N_0\)，使得当\(N > N_0\)时，\(T(N) \leq Cf(N)\)，则记为\(T(N) = O(f(N))\)。大O表示了函数T(N)增长的一个上界

  • Omega标记：如果存在正常数C和\(N_0\)，使得当\(N > N_0\)时，\(T(N) \geq Cg(N)\)，则记为\(T(N) = \Omega (g(N))\)。Omega表示了函数T(N)增长的一个下界

  • Theta标记：\(T(N) = \Theta (h(N))\)当且仅当\(T(N)=O(h(N))\)以及\(T(N) = \Omega (h(N))\)

  • 小o标记：如果对每一个正常数C，都存在常数\(N_0\)使得当\(N > N_0\)时\(T(N) < Cp(N)\)，则\(T(N) = o(p(N))\)

Definitions on Wikipedia

运算法则 如果\(T_1(N) = O(f(N)), T_2(N) = O(g(N))\)，那么有

  • \[T_1(N) + T_2(N) = O(f(N) + g(N))\]
  • \[T_1(N) * T_2(N) = O(f(N) * g(N))\]

根据上述法则，可以推导出以下结论

如果\(T(N)\)是一个k次多项式，那么\(T(N) = \Theta (N^k)\)

相对增长率是通过求解极限\(\lim_{N \to \infty} f(N)/g(N)\)得到的，该极限的求解经常需要用到洛必达法则

模型

为了分析算法在计算机中的运行特征，我们需要一个计算模型来模拟算法在计算机中的运行。为简单起见，通常我们假设模型中所有指令的运行时间是一样长的，并且模型拥有无限的内存。

需要注意的是，当不同指令之间运行时间的差异无法忽略，或者实际可用的内存有限以至于算法需要进行低速的外部存储访问（如磁盘读写）时，我们需要构造一个更复杂的计算模型来进行算法分析。

运行时间分析

可以用常数时间(O(1))内解决的问题规模来衡量算法的运行时间。

分析的法则

  • 顺序语句的运行时间是各个语句的运行时间之和

  • 分支语句的运行时间与所有分支中运行时间最大的那一个相等

  • for循环的运行时间是循环体的运行时间乘以可能的最大迭代次数

  • 对于嵌套的for循环，其运行时间是各层for循环运行时间的乘积

  • 对递归过程进行运行时间分析时，需要将递归展开。有时候递归过程展开后等价于for循环，但通常递归过程的展开会涉及一个递推关系，这时只有求解出与递归过程相对应的递推式才能分析出运行时间

  • 如果一个算法用常数时间将问题的大小削减为其一部分(比如1/2)，那么该算法就是O(logN)。另一方面，如果使用常数时间只是把问题减少一个常数的数量(如将问题减少1)，那么这种算法就是O(N)的。

进行算法分析时需要以下注意几点

  • 算法的时间复杂度分析不考虑读入数据所需要的时间。只有当数据的存取时间成为瓶颈时，才会去考虑进行IO优化。一般来说，只有算法本身足够高效才会有IO瓶颈。我们的首要目标是使得算法足够高效而不至于成为问题的瓶颈

  • 程序是算法以一种特定编程语言的实现。虽然程序的运行时间也很重要，但对于同一个算法而言，只要程序的设计是正确的，它们的复杂度都是一样的。

  • 复杂度分析通常只考虑最坏情况，因为

    • 平均情况的分析难度通常要远高于最坏情况
    • 如果最坏情况的复杂度足够好的话，那么我们可以保证算法在任意情况下的运行效率都不会太差

参考资料

猜您还喜欢