algorithm - 小 o(g(n)) 是 Theta(g(n)) 和 O(g(n)) 的集合差吗？

Question

直觉上似乎是的。谁能给个认真的证据？

Answer 1

答案是不。您需要回到每个渐近界的正式定义才能看到这一点。

Big O(g(n)) = { f(n)：存在正常数 c 和 n0 使得 0 ≤ f(n) ≤ cg(n) 对于所有 n ≥ n0}。//这是一个渐近上界。第 47 页。（见下文引文）。

Theta(g(n)) = { f(n) ：存在正常数 c1、c2 和 n0 使得 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) 对于所有 n ≥ n0}。第 44 页。 // 这是一个渐近紧界。

Little o(g(n)) = { f(n) ：对于任何正常数 c > 0，存在一个常数 n0 > 0 使得对于所有 n ≥ n0 0 ≤ f(n) < cg(n) }。第 50 页。这表示不严格的渐近上限。

Big Omega(g(n)) = { f(n)：存在正常数 c 和 n0 使得 0 ≤ cg(n) ≤ f(n) 对于所有 n ≥ n0}。第 48 页。这是一个渐近的下界。

Theta 是一个渐近紧密的上界，这意味着 Big O 和 Big Omega 必须保持，Theta 才能保持。每个定义实际上都是一个集合，因此 Theta 可以理解为集合 Big O 和 Big Omega 的并集，因此集合差异：Theta - Big O = Big Omega。不小o。

请注意，如果常量在所有集合中不保持相同，则答案会变得有点糊涂。

引文：斯坦，克利福德。“第三章功能的成长。” 算法导论。作者：Thomas H. Cormen、Charles Eric。Leiserson 和 Ronald L. Rivest。第三版。马萨诸塞州剑桥：麻省理工学院，2009 年。N. 页。打印。

Answer 2

这不是真的。拿：

f(n) = (floor(n/2))!
g(n) = (ceil(n/2))!

然后你有：

f  = O(g)      since f(n) <= g(n)
f != o(g)      since f(n) = g(n) for unbounded n (even)
f != Theta(g)  since f(n) * ceil(n/2) <= g(n) for unbounded n (odd)

所以 f 是 in O(g)\Theta(g)，但不是 in o(g)。