Problem 1 (教材习题 3.1-1)
假设 f(n) 与 g(n) 都是渐近非负函数。使用 Θ 记号的基本定义来证明
max(f(n),g(n))=Θ(f(n)+g(n))
Solution
max(f(n),g(n))=2f(n)+g(n)+2∣f(n)−g(n)∣≥21(f(n)+g(n))
且显然有
max(f(n),g(n))≤f(n)+g(n)
所以 max(f(n),g(n))=Θ(f(n)+g(n)) 。
Problem 2 (教材习题 3.1-5)
证明定理3.1(见第2讲PPT第6页或者教材3.1节)。
Solution
证明:先证充分性。由 f(n)=Θ(g(n)) ,有
∃c1>0,c2>0,n0>0,∀n≥n0,0≤c1g(n)≤f(n)≤c2g(n)
从而有 ∃c2>0,n0>0,∀n≥n0,0≤f(n)≤c2g(n) ,即 f(n)=O(g(n)) ;
且 ∃c1>0,n0>0,∀n≥n0,0≤c1g(n)≤f(n) ,即 f(n)=Ω(g(n)) 。
再证必要性。
由 f(n)=Ω(g(n)) 有 ∃c1>0,n1>0,∀n≥n1,0≤c1g(n)≤f(n) 。
由 f(n)=O(g(n)) 有 ∃c2>0,n2>0,∀n≥n2,0≤f(n)≤c2g(n) 。
取 n0=max(n1,n2)>0 ,则
∃c1>0,c2>0,n0>0,∀n≥n0,0≤c1g(n)≤f(n)≤c2g(n)
从而 f(n)=Θ(g(n)) 。
Problem 3 (教材习题 3.1-7)
证明: o(g(n))∩ω(g(n)) 为空集。
Solution
证明:反证法,假设存在 f(n) , f(n)∈o(g(n))∩ω(g(n)) ,则
f(n)∈o(g(n))⇒n→∞limg(n)f(n)=0
f(n)∈ω(g(n))⇒n→∞limg(n)f(n)=∞
从而 0=∞ ,矛盾。所以不存在这样的 f(n) ,即 o(g(n))∩ω(g(n)) 为空集。
Problem 4 (教材习题 3.1-8)
可以扩展我们的记号到有两个参数 n 和 m 的情形,其中的 n 和 m 可以按不同速率独立地趋于无穷。对于给定的函数 g(n,m) ,用 O(g(n,m)) 来表示以下函数集:
O(g(n,m))={f(n,m)∣∃c>0,n0>0,m0>0,∀n≥n0∨m≥m0,0≤f(n,m)≤cg(n,m)}
对 Ω(g(n,m)) 和 Θ(g(n,m)) 给出相应的定义。
Solution
Ω(g(n,m))={f(n,m)∣∃c>0,n0>0,m0>0,∀n≥n0∨m≥m0,0≤cg(n,m)≤f(n,m)}
Θ(g(n,m))={f(n,m)∣∃c1>0,c2>0,n0>0,m0>0,∀n≥n0∨m≥m0,0≤c1g(n,m)≤f(n,m)≤c2g(n,m)}