MIT-算法导论读书笔记-第三章.docx

MIT-算法导论读书笔记-第三章

知道插入排序的时间复杂度是O(n2)，那O记号到底是什么意思呢？本文主要介绍几个算法分析时用到的记号。
大O记号
定义：O(g(n)) = { f(n) : 存在正常数c和n0 ，使对所有的n >= n0，都有 0 <= f(n) <= cg(n) }。大O记号给出函数的渐进上界。
， 则可以表示为 f(n) = O(n2)。证明：
要使得 0 <= f(n) <= cg(n)     

存在c = 9/2 ,n0 = 1,使得对所有的n >= n0都有 0 <= f(n) <= cg(n)。
O(g(n) 以及后面讲到的记号表示的都是集合，而f(n) = O(n2)的实际意义 是 f(n) ∈ O(n2)。
假设有  ，  则 g(n) = O(n2) , f(n) = O(n2)
大Ω记号
定义：Ω(g(n)) = { f(n) : 存在正常数c和n0 ，使对所有的n >= n0，都有 0 <= cg(n) <= f(n) }。大Ω记号给出函数的渐进下界。
假设有  ，   则 g(n) = Ω(n) , f(n) = Ω(n)
大Θ记号
定义：Θ(g(n)) = { f(n) : 存在正常数c1和c2和n0 ，使对所有的n >= n0，都有 0 <= c1g(n) <= f(n) <= c2g(n) }。大Θ记号给出函数的渐进确界。
假设有  ，  则 g(n) = Θ(n) , f(n) =Θ(n2)
小O记号
定义：o(g(n)) = { f(n) : 对任意正常数c，存在n0 ，使对所有的n >= n0，都有 0 <= f(n) <= cg(n) }。小o记号给出函数的非渐进紧确的上界。
假设有  ，  则 g(n) = o(n2) , f(n) O(n2)
小记号
定义：(g(n)) = { f(n) : 对任意正常数c，存在n0 ，使对所有的n >= n0，都有 0 <= cg(n) <= f(n) }。小记号给出函数的非渐进紧确的下界。
假设有  ，  则 g(n)  (n) , f(n) = (n)
总结 并不是所有的函数都可以渐进比较的，如果 的极限值不存在（不等于0，常数以及无穷大）。比如
的极限就不存在而且不等于无穷大

Chapter3 习题答案
3.1-1 设f(n)与g(n)都是渐进非负函数。利用Θ记号的基本定义来证明max(f(n), g(n)) =Θ(f(n) + g(n))。
证明： 若证明成立，则存在n>=n0，且c1>0，c2>0： c1(f(n) + g(n)) <= max(f(n), g(n)) <= c2( f(n) + g(n) ) 成立
若max(f(n), g(n)) = f(n)，g(n) < f(n)，那么有 c1(f(n) + g(n)) <= f(n) <= c2( f(n) + g(n) ) ，转化一下
f(n) * (1 - c2) <= c2 * g(n) (1) f(n) * (1 - c1) >= c1 * g(n) (2)
再次转化，则有 g(n) >= f(n) * (1 - c2) / c2 (1) g(n) <= f(n) * (1 - c1) / c1 (2)
要使上面两个式子成立，显然 c2 >= 1，0 < c1 <= 1/2。逆向推之，必然成立。 同理可证得max(f(n), g(n)) = g(n)，f(n) < g(n)的情况。
还有一种证法，由算法导论答案提供： 存在N1，N2，当n > N1时，f(n) >= 0； 当n > N2时，g(n) >= 0。因此取N0 = max (N1， N2)，当n > N0时，有f(n) >= 0， g(n) >= 0。取c1 = 1/2，c2 = 1，由f(n)，g(n)的非负性保证，当n > N0时，有：
(f(n) + g(n)) / 2 <= max(f(n), g(n)) <= f(n) + g(n)。 因此，得证。
3.1-2 证明对任意实常数a和b，其中b>0，有 （n+a）^b = Θ（n^b）
证明：由二项式定理，有
而
显然，当n>=2|a|时，成立
此时，c1= (1/2)^b，c2=(2)^b。得证
3.1-3 解释为什么"算法A的运行时间至少是O(n^2)"这句话是无意义的。
那如果算法A的运行时间是n,O(n^2)是对于所有算法A中的输入，得到的一个最坏情况下时间的上界。也就是说n怎么也不可能超过O(n^2)吧？怎么可能是至少呢？坑爹吧
3.1-4 2^(n+1)=O(2^n)成立吗？2^(2n)=O(2^n)成立吗？
证明：若2^(n+1)= O(2^n)成立，则有存在某个正常数c，存在常数n0>0,使对于所有的n>=n0，有 0<=2^(n+1) <= c2^n 则有2<= c，成立。
若2^(2n) = O(2n)成立，则有某个正常数c成立，存在常数n0>0,使对于所有的n>=n0,有 0 <= 2^(2n) <= c 2^n 则有0 <= 2^n <= c，显然，对于指定的常数c，2^n是无限增长的，c不可能会比2^n大。so，也不成立。
3.1-5 证明定理3.1，对任意两个函数f(n)和g(n),f(n)=θ(g(n))当且仅当f(n) = O(g(n))和f(n)=Ω(g(n))
证明：正向证明：若f(n) = θ(g(n)),则有存在正常数c1,c2和n0>0，使对所有的n>=n0,有 0 <=c1g(n) <= f(n) <= c2g(n)， 此时 0 <= c1g(n) <= f(n), 0 <= f(n) <= c2g(n)， 即有 f(n) = O(g(n)) 和 f(n) = Ω(g(n))。
反向证明：若有 f(n) = O(g(n)) 和 f(n) = Ω(g(n))，则分别存在正常数c1,c2,n1>0,n2>0,使得对所有的n>=n1,n>=n2，有 0 <= f(n) <= c1g(n), 0 <= c2g(n) <= f(n)， 则存在n3>0并同时满足n3>=n2,n3>=n1，有 0 <= c2g(n) <= f(n) <= c1g(n)
由此可证，定理3.1，over.
3.1-6 证明：一个算法的运行时间是θ(g(n))当且仅当其最坏情况运行时间是O(g(n)),且最佳情况运行运行时间是Ω(g(n))。
证明：和3.1-5一个意思。
3.1-7 证明o(g(n)) ∩ω(g(n))是空集。
证明：o(g(n)) = {f(n):对任意的正常数c,存在n0>0,当n>n0，有0 <= f(n) <= cg(n)}
ω(g(n)) = {f(n):对任意的正常数c,存在n0>0,当n>n0，有0 <= cg(n) < f(n)}，显然并集为0。
3.1-8 可以将我们的表示法扩展到有两个参数n和m的情形，其中n和m的值可以以不同的速率，互相独立地趋于无穷。对给定的函数g(n,m),O(g(n,m))为函数集O(g(n,m)) = {f(n,m):存在正整数c, n0和m0，使对所有的n>=n0或者m>=m0,有0<=f(n,m)<=cg(n,m)}。
给出对应的Ω(g(n,m))和θ(g(n,m))的定义。
答: Ω(g(n,m)) = {f(n,m):存在正整数c, n0和m0，使对所有的n>=n0或者m>=m0,有0<=cg(n,m)<=f(n,m)}
θ(g(n,m)) = {f(n,m):存在正整数c1和c2, n0和m0，使对所有的n>=n0或者m>=m0,有c1g(n,m)<=f(n,m)<=c2g(n,m)}。
3-3 根据渐进增长率排序

等价类

b) n*sinn
3-4 渐进记号的性质
设f(n )和g(n)为渐进正函数。证明或否定以下的假设：
a) f(n) = O(g(n))蕴含g(n)=O(f(n)) b) f(n)+g(n)=Ф(min(f(n), g(n)))
c) f(n)=O(g(n))蕴含lg(f(n)) = O(lg(g(n)))，其中lg(g(n))>=1且f(n)>=1对足够大的n成立
d) f(n)=O(g(n))蕴含2^(f(n)) = O(2^g(n)) e) f(n)=O(f(n)^2)
f) f(n) = O(g(n))蕴含g(n) = Ω(f(n)) g) f(n) =Ф(f(n/2))
h) f(n) + o(f(n)) = Ф(f(n))
证：a)f(n) = O(g(n)),即存在某个正常数c,n0>0,当n>=n0,有 0<= cg(n) <= f(n), 此时若也存在某个正常数c',n0'>0, 当n>=n0',有 0 <= c'f(n) <= g(n)，若该不等式也满足，则有n>=max(n0,n0')，cg(n) <= f(n) <= (1/c')g(n),显然只有
f(n) = Ф(g(n))才成立，则可知题意不符。
b)f(n)+g(n)=Ф(min(f(n), g(n)))，设f(n) =Ф(min(f(n), g(n)))，即f(n) <= g(n), 则存在正常数c1,c2,n0>0,当n>=n0,有， c1*f(n) <= f(n) + g(n) <= c2*f(n)，转化，有， (c1-1)*f(n) <= g(n) <= (c2 -1)*f(n)，要使该式成立，则需要
0 <c1<= 2, 0 < g(n) <= (c2-1)f(n)。已经假设f(n) <= g(n)， f(n)、g(n)为渐进正函数, 则无论c2为何值，n>=n0, 总有g(n) >= (c2-1)f(n)。
此时矛盾，故不成立。
c) f(n)=O(g(n))蕴含lg(f(n)) = O(lg(g(n)))，其中lg(g(n))>=1且f(n)>=1对足够大的n成立
证： lg(f(n))、lg(g(n))不会改变函数的递增特性，因此成立。
d) f(n)=O(g(n))蕴含2^(f(n)) = O(2^g(n))
证：同c)
e) f(n)=O(f(n)^2)
证：假设存在正常数c, n0>0,当n>n0,有， 0 <= f(n) <= cf(n)^2, f(n)为渐进正函数，则显然有1 <= c f(n), 故题意成立。
f) f(n) = O(g(n))蕴含g(n) = Ω(f(n))
证：假设存在正常数c, n0>0,当n>n0,有， 0 <= f(n) <= cg(n),转化，有， 0 <= (1/c)f(n) <= g(n),显然题意成立，有g(n) = Ω(f(n))。
g) f(n) = Ф(f(n/2))
证：假设存在正常数c1，c2, n0>0,当n>n0,有， c1*f(n/2) <= f(n) <= c2*f(n/2),
由于n > n/2, 有f(n) > f(n/2)，则0 <c1<=1,有， c1*f(n/2) <= f(n) ， c2 >= f(n)/f(n/2)，若n->正无穷，则存在渐进函数f(n)= a^x, f(n)->正无穷。因此不符合题意。
h) f(n) + o(f(n)) = Ф(f(n))
证：假设存在正常数c1，c2, n0>0,当n>n0,有， c1*f(n) <= f(n)+o(f(n)) <= c2*f(n),转化，有 (c1-1)*f(n) <= o(f(n)) <= (c2-1)*f(n)
已知有任意正常数c, n1>0,当n>n1，有， 0 <=o (f(n)) <= c*f(n)， 由于c是任意正常数，显然与上述描述矛盾。因此不成立。