算法(4th ed)(152):基础——算法分析 6.3.1

阅读数:6 2019 年 11 月 6 日 07:52

算法(4th ed)(152):基础——算法分析 6.3.1

(数学模型:近似)

这种频率分析可能会产生复杂冗长的数学表达式。例如,刚才我们所讨论的 ThreeSum 中的 if 语句的执行次数为:

N(N1)(N2)/6=N3/6N2/2+N/3

一般在这种表达式中,首项之后的其他项都相对较小(例如,当 N=1000 时,N2/2+N/3499 667,相对于 N3/6166 666 667 就小得多了),如图 1.4.3 所示。我们常常使用约等于号(~)来忽略较小的项,从而大大简化我们所处理的数学公式。该符号使我们能够用近似的方式忽略公式中那些非常复杂但幂次较低,且对最终结果的贡献无关紧要的项:

定义。我们用 f(N) 表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。我们用 g(N)f(N) 表示 g(N)/f(N) 随着 N 的增大趋近于 1。

算法(4th ed)(152):基础——算法分析 6.3.1

图 1.4.3 首项近似

例如,我们用 N3/6 表示 ThreeSum 中的 if 语句的执行次数,因为 N3/6N2/2+N/3 除以 N3/6 的结果随着 N 的增大趋向于 1。一般我们用到的近似方式都是 g(N)af(N),其中 [f(N)=Nb(logN)c,其中 a、b 和 c 均为常数。我们将 f(N) 称为 g(N)增长的数量级(如表 1.4.2 所示)。我们一般不会指定底数,因为常数 a 能够弥补这些细节。这种形式的函数覆盖了我们在对程序运行时间的研究中经常遇到的几种函数,如表 1.4.3 所示(指数级别是一个例外,我们会在第 6 章中讲到)。我们会详细说明这几种函数并在处理完 ThreeSum 之后简要讨论为什么它们会出现在算法分析领域之中。

表 1.4.2 典型的近似

函数 近似 增长的数量级
N3/6N2/2+N/3 N3/6 N3
N2/2N/2 N2/2 N2
lgN+1 lgN lgN
3 3 1

表 1.4.3 常见的增长数量级函数

增长的数量级
描述函数
常数级别1
对数级别logN
线性级别N
线性对数级别NlogN
平方级别N2
立方级别N3
指数级别2N

评论

发布