algorithm - 大 O 还是大 theta？

Question

假设我们有一个函数 f(n)= log n 和另一个函数 g(n)=log n^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)) 成立。直观上 big-oh 意味着 f 受 g(n) 的限制(即它的增长不比 g 快)。另一方面，大 theta 意味着 f 上下都受 g 的限制(即它的增长速度与 g 一样快)。请注意最后两句不是绝对准确的，目的是为了更容易理解和关注这个的直观含义而不是它的理论。