algorithm - 函数 (log n)^k 的大 O 是什么

Question

对于任意 k，函数 (log n)^k 的大 O 复杂度是多少？

Answer 1

任何运行时形式为 (log n)^k 的函数都是 O((log n)^k)。使用简单的转换，此表达式无法还原为任何其他原始函数，并且经常看到运行时间为 O(n (log n)²) 的算法。具有这种增长率的函数称为多对数函数。

顺便说一下，通常 (log n)^k 写成 log^k n，所以上面的算法的运行时间为 O(n log² n。在您的情况下，函数 log² n + log n 将为 O(log² 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，则在这种情况下正确的大 O 计算将是 O(k log n)。

根据您工作的环境，您有时会看到符号 Õ(f(n)) 表示某个常量 k 的 O(f(n) log^k n)。这有时称为“soft-O”，用于与对数项无关的上下文中。在这种情况下，您可以说这两个函数都是 Õ(1)，尽管这种用法在简单的算法分析中并不常见(事实上，在维基百科之外，我只看到过一次这种用法)。

希望这对您有所帮助!