知识星球算法时空，练习题目解答

exercise-渐近记号练习.md

---

date：2017-11-07 title：渐近记号练习

题目

I. 写出下列式子的 ⍬ 记号

• T1(n) = 4nlogn + 700n
• T2(n) = 5nlogn + 3n^3 + 25n - 7
• T3(n) = 2n^2 + 2^n

II. 写出下列式子的 O 记号

T4(n) = 1^3 + 2^3 + 3^3 + ... + n^3

III. 总耗时计算

对于某集合，若当前元素个数为 M 时，在其中放入新元素耗时 alogM, a 是常数，那么，从空集开始一直放入，最后内有 n 个元素。总耗时多少？写出 ⍬ 记号。

---

解答

I. 写出下列式子的 ⍬ 记号

T1(n)，nlogn

T2(n)，n^3

T3(n)，2^n

II. 写出下列式子的 O 记号

T4(n)，O(n^4)

证明：
1^3 + 2^3 + 3^3 + ... + n^3
 = (1+n)(1^2 + n^2 - n) + (1+n)(2^2 + (n-1)^2 - 2(n-1)) ... # 利用立方和公式，组合第一个和倒数一个元素，组合第二个和倒数第二个元素
 = (1+n)(1^2 + 2^2 + ... + n^2 - n - 2(n-1) - ...)
 <= (1+n)(1^2 + 2^2 + ... + n^2 - n * n) # 利用 n < (n^2)/2，将 -n - 2(n-1) - 3(n-2) ... < -n - n - n ... = - n * n 代入
 = (1+n)(n-1)n(2n-1)/6 # 平方和公式
 <= n^4

III. 总耗时计算

T5(n)，⍬(nlogn)

a(log1 + log2 + ... + logn)
 = a(log(n!))
 = ⍬(nlogn)