对于任何 k ，函数 (log n) k的大 O 复杂度是多少？
问问题
80918 次
4 回答
37
任何运行时格式为 (log n) k的函数都是 O((log n) k )。这个表达式不能使用简单的转换简化为任何其他原始函数，并且看到像 O(n (log n) 2 ) 这样的运行时算法是相当普遍的。具有这种增长率的函数称为多对数函数。
顺便说一句，通常 (log n) k写为 log k n，因此上述算法的运行时间为 O(n log 2 n。在您的情况下，函数 log 2 n + log n 将是 O(log 2 n ）。
但是，任何具有 log (n k ) 形式的运行时的函数都有运行时 O(log n)，假设 k 是一个常数。这是因为 log (n k ) = k log n 使用对数恒等式，并且 k log n 是 O(log n) 因为 k 是常数。但是，您应该注意不要盲目地得出 O(log (n k )) 的算法是 O(log n) 的结论；如果 k 是函数的参数或取决于 n，则在这种情况下，正确的 big-O 计算将是 O(k log n)。
根据您工作的环境，您有时会看到符号 Õ(f(n)) 表示某个常数 k 的 O(f(n) log k n)。这有时被称为“ soft-O ”，用于对数项不相关的上下文中。在这种情况下，您可以说这两个函数都是 Õ(1)，尽管这种用法在简单的算法分析中并不常见（事实上，在 Wikipedia 之外，我已经看到它恰好使用过一次）。
希望这可以帮助！
于 2011-09-23T00:42:07.007 回答
5
(log n)^k 是：
- O((log n)^k)
- O(n^k)
- 上）
- O(n log n)
- O(n^1/2)
- O(n^0.00000002)
等等。哪一个对您有意义取决于常量和上下文。
于 2011-10-01T17:50:15.077 回答
5
它仍然是(log(n))^2。一个对数的幂已经是最低/最简单的形式。
于 2011-09-23T00:40:30.217 回答
4
log(n)所以O((log(n))^2)整个表达式是O((log(n))^2)
于 2011-09-23T00:47:26.997 回答