第二章为“算法分析”,该部分主要介绍了计算机科学中目前用于测量一个算法的运行复杂的具体数学方法;同时给出了多个问题示例,对每个问题分别采用不同复杂度的算法,可以直观地了解到在解决实际问题时,不仅仅需要能够得出结果的算法,更应该给出算法复杂度更低的算法的意义
数学工具:“大O”表示法,用于估计一个程序运行所需要的时间问题示例:采用更优的算法,使得解决问题所需要的时间缩短几个量级递归函数:举例说明不良的递归导致算法所复杂度极高以上四个定义中用于建立不同函数间运行时间的相对级别,称为大O描述法。其中T(N)为函数的运行时间,N为运算的规模,如循环的次数,数组大小等等。比较两个函数在某个N下的实际运行时间值的绝对值的意义是不大的,因为程序运行的时间会受到很多特殊因素的影响,如循环中判断是否应跳出循环,一个大的运算每次附带的一个单次运算,这些特殊因素在N较大时对T(N)几乎没有影响,但在N较少时可能会占据 较大比例;而且很多情况下程序会走向不同的分支,其执行时间是不一致的,也很难精确统计其运行时间。
大O描述则提供了一种反映函数计算时间的增长率的方法,其定义用极限可以表示为:若T(N)=O(f(N)), 则
limn→+∞T(N)f(N)=X 其中X为0或者常数, 从直观的角度可以理解为当N很大时,T(N)比f(N)数量级相等或更小。有一点需要注意的是,若T(N)=N,则T(N)=O(N^2)和T(N)=O(N)均是成立的,但很显然只有后者是有意义的,因为O()包含了一个“大于等于”的含义,因此实际中是需要尽可能找到数量级相等的情况,换句话说,应该找到 T(N)=Θ(h(N)) ,使用大O一方面是因为惯例,另外一方面是因为很多时候我们不能确定得到的h(N)是和T(N)等数量级的而只能确定其数量不会超过h(N)
对于大O估算而言基本公式有两个,若 T1(N)=O(f(N)),T2(N)=O(g(N)) 则:
T1(N)+T2(N)=max(O(f(N)),O(g(N))) T1(N)∗T2(N)=O(f(N)∗g(N))而对于大多数程序函数而言,其可能的复杂度形式有以下几种:
复杂度名称 c 常数级 logN对数级 log2N 对数平方级 N 线性级 NlogN对数线性级 N2 平方级 N3 立方级 2N 指数级其中复杂度从上到下依次递增,对于实际可用的程序而言指数级往往是不可接受的,计算机实际能解决的问题目前只限于多项式复杂度以下,即 O(Nk) 复杂度以下,这些能用多项式复杂度解决的问题称为P问题(Polynomial),不确定是否能找到多项式复杂度解法的问题称为NP问题(Nondeterministic Polynomial),而研究NP问题是否存在P算法则是计算机科学的一个非常重要的研究方向,因为现实中大多数问题均是NP问题。 而对于以上这些常见复杂度形式又有以下两个经验公式可以用于进行复杂度的比较:
若T(N)为一个N次多项式,则 T(N)=Θ(Nk) ` ∀k∈R,logkN=O(N) ,即log函数增长是非常缓慢的以上是书上给出的公式,同时我自己在解题时也发现了一些没有经过严格证明的经验公式,大家可以参考:
∀k∈R,k>0;logN=O(Nk) ∀k1,k2∈R,k1,k2>0;logk1N=O(Nk2)此外一个关于调和级数的求和公式也常常用到:
∑i=1N1i=lnN+γ 其中 γ 为欧拉常数,约为0.57721.