计算机算法设计与分析(第4版)王晓东习题解答.pdf

计算机算法设计与分析(第4版)-王晓东习题解答第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得nn0，有fc1*g(n)。由于c10，故g(n)1/c1*f(n)，故g=Ω(f)。必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得nn0，有g(n)c2*f(n).由于c20，故f(n)1/c2*f(n)，故f=Ο(g)。2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和