3.1-1:
假设0⩽c1(f(n)+g(n))⩽max(f(n),g(n))⩽c2(f(n)+g(n))
∴0⩽c1(x+y)⩽x+y+|x−y|2⩽c2(x+y)
∵0⩽|x−y|⩽x+y
∴0⩽12(x+y)⩽x+y+|x−y|2⩽x+y
∴c1=12,c2=1
3.1-2
假设0⩽c1(nb)⩽(n+a)b⩽c2(nb)∵n+a⩽n+|a| n+a>0 ∴|a|⩽n∴n+a⩽2n ∵n+a⩾0 n+a⩾n−|a| ∴n+a⩾n−|a|∴n+a⩾12n(如果不引入a的情况下)||n+a⩾1|a|+1n∴c1=12||1|a|+1 , c2=2,n0=2|a| || |a|+1
3.1-3
O(n2)
是一个Set并不是具体的运行时间，如果要转换，则运行时间是
0⩽f(n)⩽c2g(n),T(n)⩾f(n)
是没有意义的
3.1-4
∵2n+1=O(2n)∴2∗2n=c22n∴c2=2∵22n=O(2n)∴22n=c22n∴2n=c2∵0<n<∞且c2是常量∴22n≠O(2n)
3.1-5
定理证明需要充分性和必要性：
充分性：
由f(n)=Θ(g(n))得f(n)=O(g(n))且f(n)=Ω(g(n));根据Θ定义：有N0,C0,C1,使得：当n>N0有C0g(n)⩽f(n)⩽C1g(n),再根据O和Ω定义可得f(n)=O(g(n))且f(n)=Ω(g(n))
必要性：
由f(n)=O(g(n))且f(n)=Ω(g(n))推出f(n)=Θ(g(n));根据O和Ω定义有：存在N1,C1使得：当n>N1有f(n)⩽C1g(n);存在N2,C0使得：当n>N2有f(n)⩾C0g(n);设N0=max(N1,N2),则当n>N0,有：C0g(n)⩽f(n)⩽C1g(n),即f(n)=Θ(g(n))
所以，得证
3.1-6
可易证，根据定义
Θ
给出了上下边界，而
O,Ω
分别定义了上下边界
3.1-7
∵letf∈(g(n))∩ω(g(n))∴f=o(g(n))=ω(g(n))∵o=limn→∞f(n)g(n)=0;ω=limn→∞f(n)g(n)∴o≠ω∴f=null
3.1-8
Ω(g(n,m))={f(n,m):constants:c,n0,m0;if:n⩾n0 and m⩾m0;thus:0⩽cg(n,m)⩽f(n,m);}
