【算法分析与设计】第2篇：计算模型与渐进复杂性分析

上一篇我们确立了算法评价的三个维度正确性、效率与最优性。但当我们声称“算法A比算法B快”时这句话究竟是什么意思同一个算法在笔记本电脑和超级计算机上运行的秒数不同用秒表衡量算法效率显然毫无意义。我们需要一个独立于硬件性能的尺度这便是计算模型的任务。计算模型的核心功能是将“执行一个操作”抽象为可计量的基本单位。本文介绍两种最主流的模型。第一种是图灵机模型。它的结构极为朴素一条无限长的纸带被划分为一个个格子一个读写头在纸带上左右移动根据当前状态和读取到的符号决定写入什么、如何移动以及跳到什么状态。听起来笨拙但Church-Turing论题断言任何在物理世界中可计算的问题图灵机都可计算。它的价值在于界定“可计算性”的理论边界但在日常的算法分析中用图灵机去描述一个排序过程显然是杀鸡用牛刀。因此实际分析中更常用的是第二种——RAM模型即随机存取机器模型。它假设我们有一台理想化计算机每个简单操作算术运算、比较、赋值、内存存取等都花费一个单位时间每条简单指令顺序执行没有缓存未命中没有流水线停顿。虽然真实机器远比这复杂但RAM模型抓住了计算量的核心趋势使得跨语言、跨平台的算法效率比较成为可能。建立在计算模型之上我们就获得了刻画渐进复杂度的数学语言。下面给出五种渐进记号的严格定义。设n为输入规模f(n)和g(n)均为非负函数。O记号大O上界f(n)O(g(n))当且仅当存在正常数c和n₀使得对所有n≥n₀有f(n)≤c·g(n)。它描述的是“算法最慢不会慢过多少”是最常用的上界标记。比如遍历数组耗时2n3步我们说它是O(n)的。Ω记号大Ω下界f(n)Ω(g(n))当且仅当存在正常数c和n₀使得对所有n≥n₀有f(n)≥c·g(n)。它回答“算法至少要做多少工作”比如基于比较的排序算法下界是Ω(n log n)。Θ记号大Θ紧确界f(n)Θ(g(n))当且仅当同时存在正常数c₁、c₂和n₀使得对所有n≥n₀有c₁·g(n)≤f(n)≤c₂·g(n)。它锁定了一个函数的精确增长阶是我们最希望给出的结论——既不太松也不太紧。o记号小o非紧上界f(n)o(g(n))当且仅当对任意正常数c总存在n₀使得n≥n₀时f(n)c·g(n)。它比大O更强表示f(n)的增长严格慢于g(n)比如n log no(n²)。ω记号小ω非紧下界f(n)ω(g(n))当且仅当对任意正常数c总存在n₀使得n≥n₀时f(n)c·g(n)。与大Ω的界限可以相等不同小ω要求f(n)的增长严格快于g(n)。在这套记号的帮助下我们可以在三个层面描述算法的复杂度。最好情况复杂度是算法在最优输入下的表现。它往往很漂亮但没什么实用价值——极少有人会指望输入数据恰好排好序。最坏情况复杂度是算法在最劣输入下的表现它提供了一个铁定的上限保证无论输入多么刁钻算法的运行时间都不会超过这个量级。这是工程中最受重视的指标。而平均情况复杂度是对所有可能输入按其概率分布加权求期望。它更贴近日常表现但需要假设输入服从某种分布分析过程也往往需要复杂的数学技巧。接下来的学习中你会反复看到我们讨论复杂度时绝大多数时候说的都是最坏情况下的渐进上界也就是最坏情况的大O。这并非因为其他指标不重要而是因为它给出了最可靠的安全承诺。从下一篇开始我们将带着这套分析工具进入第一个具体的算法设计主题——递归以及它背后的数学语言递归方程。