f(n)=O(g(n))、f(n)=Ω(g(n))、f(n)=Θ(g(n))等的含义
时间: 2023-12-03 13:06:28 浏览: 42
f(n) = O(g(n)) 表示存在正常数 c 和 n0,使得当 n ≥ n0 时,f(n) 的值不超过 g(n) 的值的 c 倍。也就是说,f(n) 的增长率不会比 g(n) 的增长率快。
f(n) = Ω(g(n)) 表示存在正常数 c 和 n0,使得当 n ≥ n0 时,f(n) 的值至少为 g(n) 的值的 c 倍。也就是说,f(n) 的增长率不会比 g(n) 的增长率慢。
f(n) = Θ(g(n)) 表示存在正常数 c1,c2 和 n0,使得当 n ≥ n0 时,f(n) 的值在 c1 倍 g(n) 的值和 c2 倍 g(n) 的值之间。也就是说,f(n) 的增长率和 g(n) 的增长率是相等的,它们的渐进增长率相同。
相关问题
f(n)=nlogn的tight bound
f(n)=nlogn的tight bound是O(nlogn)和Ω(nlogn)。
证明如下:
O(nlogn)证明:
对于任意n>1,由于logn是单调递增的,因此有
nlogn ≤ nlogn + nlogn + … + nlogn (共logn个nlogn)
= nlogn
因此,f(n)=nlogn是O(nlogn)的。
Ω(nlogn)证明:
我们需要找到一个常数c和一个整数n0,使得对于所有的n≥n0,都有f(n)≥c⋅nlogn。
考虑取c=1/2,n0=2。对于n≥n0,有:
f(n) = nlogn = logn^(n) ≥ log2^(n) = nlog2
又因为log2是一个常数,因此有
f(n) ≥ 1/2⋅nlogn
故f(n)=nlogn是Ω(nlogn)的。
对于下列各组函数 f(n)和 g(n),确定 f(n)=O(g(n))或 f(n)=Ω(g(n))或 f(n)=θ(g(n)), 并简述理由。
1. f(n) = n^2 + 2n + 1, g(n) = n^2
f(n) = n^2 + 2n + 1 <= 4n^2 for n >= 1
Therefore, f(n) = O(g(n))
2. f(n) = nlogn, g(n) = n
f(n) = nlogn >= n for n >= 1
Therefore, f(n) = Ω(g(n))
3. f(n) = n^3, g(n) = n^2
f(n) = n^3 >= n^2 for n >= 1
Therefore, f(n) = Ω(g(n))
4. f(n) = 2^n, g(n) = 3^n
As f(n) and g(n) are exponential functions with different bases, it is not possible to compare them using big-O, big-Ω, or big-θ notations.