Big O还是Big theta？

Question

假设我们有一个函数f(n)= log，另一个函数g(N)=logn^2，问题是f(n)=O(g(n))还是f(n)=big_Theta(g(n))。由于log n^2 =2 log n，那么我的问题的另一种方式是，我们可以使用分数作为常数k吗？对于big_Theta选项，下限为k1=1/4，上限为k2=1。这样可以吗？

显然，k不能是零或负，但我对分数不确定，我在网上或我看过的书中也看不到明确的答案。

提前感谢您的帮助。

Answer 1

f(n)=Θ(g(n))和f(n)=Θ(g(n))。同时请注意，f(n)=O(g(n))也是真的。直觉上的大-oh意味着f的上界是g(N)(即它的增长速度不会快于g)。另一方面，大θ意味着f在g之上和之下都有界(即它的增长速度恰好与g一样快)。请注意，最后两句并不是绝对精确的，目的是为了更容易理解，并专注于这一点的直观含义，而不是它的理论。