如何证明对数函数的复杂性？

Question

假设你有两个对数函数，比如

​

如果f(n)是O(g(n))Ω(g(n))或Θ(g(n))，你会怎么做？当你比较两个指数方程时，我发现这样的问题比较容易，因为例如当x(n) = n^2和p(n) = n^2时，你可以找到一个c>0(Ex3)，其中x(n) <= cp(n)，其中所有n大于某个n>0，这将证明x(n) = O(p(n))。然而，由于某些原因，比较两个对数函数似乎要困难得多。感谢您的帮助，谢谢！

Answer 1

f(n)为O(g(n))当且仅当存在a常数c和n_0，使得每个n >= n_0的f(n) <= c * g(n)。f(n)是Ω(g(n))当且仅当存在常数c和n_0，使得对每个n >= n_0都有f(n) >= c * g(n)。

现在，f(n)是Θ(g(n))当且仅当f(n)是O(g(n))，f(n)是Ω(g(n))。

因此，在您的案例中，我们有：

f(n) = log (n^2) = 2logn

也就是说，g(n)是logn和c = 2，也就是f(n) <= 2 * logn和f(n) >= 2 * logn，这就是Ω(logn)。

顺便说一句。它也是f(n) <= n和f(n) >= 1，所以f(n)可以是O(n)，但我们不使用它，因为我们可以找到更好的O(g(n))。在这种情况下，我们在两个符号中没有相同的函数，对于这些值，我们没有Ω。但是，我们只需要一个选项让g(n)声明Ω。如果我们找不到它，我们就说它不是Ω。注意“我们说”这个词。

在第二种情况下，我们只关心“最高增长价值”，即logn部件。现在是c = 1和g = log(n)，所以在本例中，它也是Ω(logn)。