什么是函数的大O(log n)^ 2 + logn

Question

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

Answer 1

运行时格式为(log n)^k的任何函数都是O((log n)^k).这个表达式不能使用简单的转换减少到任何其他原始函数,并且看到像O(n(log n)²)这样的运行时算法是相当常见的.具有此增长率的函数称为polylogarithmic.

顺便说一下,通常(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,则在这种情况下正确的big-O计算将是O(k log n).

根据您工作的上下文,您有时会将符号Õ(f(n))视为某个常数k的O(f(n)log ^k n).这有时被称为" soft-O ",并且用于对数项不相关的上下文中.在这种情况下,你可以说这两个函数都是Õ(1),虽然这种用法在简单的算法分析中并不常见(实际上,在维基百科之外,我已经看过这个用法恰好一次).

希望这可以帮助!

Answer 2

(log n)^ k是:

• O((log n)^ k)
• 为O(n ^ k)的
• 上)
• O(n log n)
• 为O(n ^ 1/2)
• 为O(n ^ 0.00000002)

哪一个对你有意义取决于常数和背景.

Answer 3

它仍然会(log(n))^2。对数的幂已经是最低/最简单的形式。

Answer 4

log(n)是O((log(n))^2)这样整个表达式是O((log(n))^2)