函数的big-O是什么(log n)^ k [英] What is the big-O of the function (log n)^k

问题描述

对于任何k，函数(log n) ^k 的big-O复杂度是多少?

What is the big-O complexity of the function (log n)^k for any k?

推荐答案

任何运行时格式为(log n) ^k 的函数均为O((log n) ^k ).使用简单转换无法将该表达式还原为任何其他原始函数，并且看到带有O(n(log n) ² )这样的运行时的算法是相当普遍的.具有这种增长率的函数称为 polylogarithmic.

Any function whose runtime has the form (log n)^k is O((log n)^k). This expression isn't reducable to any other primitive function using simple transformations, and it's fairly common to see algorithms with runtimes like O(n (log n)²). Functions with this growth rate are called polylogarithmic.

顺便说一句，通常(log n) ^k 被写为log ^k n，因此上述算法的运行时间为O(n log ² n.在您的情况下，函数log ² n + log n将为O(log ² n).

By the way, typically (log n)^k is written as log^k n, so the above algorithm would have runtime O(n log² n. In your case, the function log² n + log n would be O(log² n).

但是，假设k是一个常数，任何运行时格式为log(n ^k )的函数都具有运行时O(log n).这是因为使用对数恒等式，log(n ^k )= k log n，并且因为k是常数，所以k log n为O(log n).但是，请注意不要盲目得出结论，算法为O(log(n(s s ))为O(log n).如果k是函数的参数或依赖于n，则在这种情况下正确的big-O计算应为O(k log n).

However, any function with runtime of the form log (n^k) has runtime O(log n), assuming that k is a constant. This is because log (n^k) = k log n using logarithm identities, and k log n is O(log n) because k is a constant. You should be careful not to blindly conclude that an algorithm that is O(log (n^k)) is O(log n), though; if k is a parameter to the function or depends on n, the correct big-O computation would be O(k log n) in this case.

根据您所处的工作环境，有时会看到符号Õ(f(n))表示某个常数k的O(f(n)log ^k n).有时称为" soft-O "，并且在上下文中使用其中对数项无关紧要.在那种情况下，您可以说两个函数都是Õ(1)，尽管这种用法在简单的算法分析中并不常见(实际上，在Wikipedia之外，我已经看到它只使用了一次).

Depending on the context in which you're working, you sometimes see the notation Õ(f(n)) to mean O(f(n) log^k n) for some constant k. This is sometimes called "soft-O" and is used in contexts in which the logarithmic terms are irrelevant. In that case, you could say that both functions are Õ(1), though this usage is not common in simple algorithmic analysis (in fact, outside of Wikipedia, I have seen this used precisely once).

希望这会有所帮助！

这篇关于函数的big-O是什么(log n)^ k的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！