Skip to content

Latest commit

 

History

History
88 lines (57 loc) · 3.24 KB

3.1.md

File metadata and controls

88 lines (57 loc) · 3.24 KB

Exercises 3.1-1


Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Θ- notation, prove that max(f(n), g(n)) = Θ(f(n) + g(n)).

Answer

我们需要证明 c1(f(n) + g(n)) <= max(f(n), g(n)) <= c2(f(n) + g(n))

因为f和g都是非负函数,只需要令c1 = 0.5, c2 = 1即可.

Exercises 3.1-2


Show that for any real constants a and b, where b > 0,

Answer

需要证明 c1n^b <= (n+a)^b <= c2n^b

在 n > 2|a| 时, 令 c1 = 0.5, c2 = 2 即可.

Exercises 3.1-3


Explain why the statement, "The running time of algorithm A is at least O(n^2)," is meaningless.

Answer

O-notation确定的是一个上界,而at least确定的是一个下界

Exercises 3.1-4


Is Is

Answer

(1)成立,因为当c0=2时,对所有的n>=1有0<=2^(n+1)<=2*2^n。

(2)不成立,假设存在常数c使得2^(2n)<=c2^n,则有2*n<=lg c+n,即n<=lg c,并不存在一个常数c使得这个不等式对n成立。

Exercises 3.1-5


Prove Theorem 3.1. For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

Answer

充分性:f(n)=Θ(g(n))意味着存在c1、c2和n0(其中n>=n0)使得0<=c1g(n)<=f(n)<=c2g(n)。我们由此可推出以下两个结论:

  • 存在c1和n0(其中n>=n0)使得0<=c1g(n)<=f(n),即f(n)=Ω(g(n))
  • 存在c2和n0(其中n>=n0)使得0<=f(n)<=c2g(n),即f(n)=O(g(n))

必要性:f(n)=Ω(g(n))意味着“存在c1'和n1(其中n>=n1)使得0<=c1'g(n)<=f(n)”。类似的,f(n)=O(g(n))意味着“存在c2'和n2(其中n>=n2)使得0<=f(n)<=c2'g(n)”。 令c1=c1',c2=c2',n0=max{n1, n2},由Θ的定义我们有:f(n) = Θ(g(n))。

Exercises 3.1-6


Prove that the running time of an algorithm is Θ(g(n)) if and only if its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).

Answer

Theorem 3.1.

Exercises 3.1-7


Prove that o(g(n)) ∩ ω(g(n)) is the empty set.

Answer

假设o(g(n)) ∩ ω(g(n))不是一个空集,则等价于说:对于所有的c1,c2>0有0<=c1g(n)<f(n)<c2g(n)其中n>=max(n1, n2)。

我们令c1=c2,可以得出悖论,因此假设不成立,所以o(g(n)) ∩ ω(g(n))是一个空集。

Exercises 3.1-8


We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions

O(g(n, m)) = {f(n, m): there exist positive constants c, n0, and m0 such that 0 ≤ f(n, m) ≤ cg(n, m)for all n≥n0 and m≥m0}.

Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).

Answer

Ω(g(n,m)={f(n,m):there exist positive constants c,n0, and m0 such that 0 ≤ cg(n,m) ≤ f(n,m) for all n≥n0 and m≥m0.

Θ(g(n,m)={f(n,m):there exist positive constants c1,c2,n0, and m0 such that 0 ≤ c1g(n,m) ≤ f(n,m) ≤ c2g(n,m) for all n≥n0 and m≥m0.


Follow @louis1992 on github to help finish this task.