2020/10/28:初稿，參考https://ita.skanev.com/，修訂參考文獻的部分錯誤

2020/10/30:修訂第二節第4題的證明錯誤(參考https://blog.csdn.net/qq_36414798/article/details/81028403)

3 Growth of Functions

3.1 Asymptotic notation

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

From asymptotically nonnegative, we can assume that:

Let??, some obvious things for?:

From the last two inequalities, we get:

Which is the definition of?with?

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

The most significant term is? and this is obviously polynomially tightly bound.

3.Explain why the statement, "The running time of algorithm?A?is at least??is meaningless.

The?O-notation provides an upper bound. "At least" implies a lower bound.

4.Is? ? Is?

Yes, because if we choose?2?for both constants in the?O-notation definition, we get an equality.

No, because?

5.Prove Theorem 3.1

The theorem states:

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))

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)).

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

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?O(g(n,m))?the set of functions:

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

3.2 Standard notations and common functions

1.Show that if?f(n)?and?g(n)?are monotonically increasing functions, then so are the functions?f(n)+g(n)?and?f(g(n)), and if?f(n)?and?g(n)?are in addition nonnegative, then?f(n)?g(n)?is monotonically increasing.

2.Prove equation (3.16)

3.Prove equation (3.19). Also prove that?n!=ω()?and?n!=o().

?4.Is the function??lgn?!?polynomially bounded? Is the function??lglgn?!?polynomially bounded?

?lgn?! is not polynomially bounded, but ?lglgn!??is.

If we take the definition of polynomially bound:

and take the logarithm of each side, we get:

Thus, a function is polynomially bound if?

In the following proofs, we will make use of the following two facts:

lg(n!) =?Θ(nlgn) (by equation (3.19))

?lgn??=?Θ(lgn), because

· ?lgn???≥?lgn

· ?lgn???≤?lgn + 1?≤?2lgn,?for all n?≥?2

lg(?lgn?!) =?Θ(?lgn?lg?lgn?) =?Θ(lgn lg lgn) =?ω(lgn).Therefore, lg(?lgn?!)?≠ Ο(lgn), and so??lgn?! is not polynomially bounded.

lg(?lglgn?!) =?Θ(?lglgn?lg?lglgn?) =?Θ(lglgn lg lglgn) =? =? ??=?ο(lgn) .

The last step above follows from the property that any polylogarithmic function grows more slowly than any positive polynomial function, i.e., that for constants a, b?＞?0, we have =?. Substitute lgn for n, 2 for b, and 1 for a, giving.

Therefore, lg(?lglgn?!) =?Ο(lgn), and so??lglgn?! is polynomially bounded.

5.?Which is asymptotically larger:

The second, because:

6.Show that the golden ratio???and its conjugate??both satisfy the equation?.

7.Proove by induction that the?ith Fibonacci number satisfies the equality

Base:

Step:

8.Show that??implies?.

Problem

3.1?Asymptotic behavior of polynomials

3.2?Asymptotic behavior of polynomials

Indicate for each pair of expressions?(A,B)?in the table below, whether?A?is?O,?o,?Ω,?ω, or?Θ?of?B. Assume that?k≥1,??>0, and?c>1?are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.

Note:

3.3 Ordering by asymptotic growth rates.?

a.Rank the following functions by order of growth;that is, find an arrangement??of the functions?. Partition your list into equivalence classes such that functions?f(n)?and?g(n)?are in the same class if and only if?.

b.Give an example of a single nonnegative function?f(n)?such that for all functions?gi(n)?in part (1),?f(n)?is neither??nor?.

The order is thus:

The asked function can be:

3.4 Asymptotic notation properties

3.5?Variations on?O?and?Ω

3.6?Iterated functions

總結

以上是生活随笔為你收集整理的算法导论第三版 第3章习题答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。