算法复杂度比较：七对表达式的渐进符号分析

本题分析以下七对表达式之间的渐进符号关系（Big O, Big Omega, Theta）：

(a) A=n³ - 100n, B= n² +50n

(b) A = log₂(n²), B = log₂.₇(n⁴)

(c) A = 10¹⁰⁰⁰⁰⁰, B = n

(d) A = 2ⁿlogn, B = n¹⁰ + 8n²

(e) A = 2ⁿ, B = 2ⁿ+logn

(f) A = 33ⁿ,B = 32ⁿ

(g) A = (√2)logn, B = √log n

答案：

(a) A = O(B), A = Ω(B), A = Θ(B)

(b) A = O(B), A = Ω(B), A = Θ(B)

(c) A = O(1), A = Ω(1), A = Θ(1)

(d) A = Ω(B)

(e) A = O(B), A = Ω(B), A = Θ(B)

(f) A = Ω(B)

(g) A = Ω(B)

解析:

Big O 表示法：描述函数在最坏情况下增长速度的上限。* Big Omega 表示法：描述函数在最好情况下增长速度的下限。* Theta 表示法：当函数的增长速度上限和下限相同时使用。

例如，对于表达式 (a)，A 和 B 都是关于 n 的多项式，且 A 的最高次项大于 B 的最高次项，因此 A 的增长速度比 B 快，所以 A = Ω(B)。同时，由于 Big O 是 Big Omega 的反向关系，所以 A = O(B)。因为 A 既是 B 的上限也是下限，所以 A = Θ(B)。

对于其他表达式，我们也可以根据定义和函数的性质进行类似的分析。