什么是大O的功能（log n）的^ 2 + LOGN的 [英] What is the big-O of the function (log n)^2 + logn

问题描述

什么是功能的大O的复杂性（log n）的 ^K 对任意k？

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

推荐答案

，其运行时的任何函数的形式（log n）的 ^K 为O（（log n）的 ^K ）。通过简单的转换这EX pression不reducable任何其他原始功能，这是相当普遍的看到算法，运行时就像为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 写成日志 ^K N，所以上述算法将有运行时为O（n日志 ² ñ。在你的情况，功能日志 ² N +日志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 ）具有运行时间为O（log n）的，假设k为常数。这是因为的log（n ^K ）= K日志N使用对数的身份，并且k日志n为0（log n）的，因为k是常数。您应该谨慎，不要盲目断定的算法是O（日志（N ^K ））为O（log n）的，虽然，如果k是一个参数的函数或依赖于N，正确的大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.

这取决于你的工作环境中，你有时会看到乐谱O（F（N））的意思O（F（N）日志 ^K N）为一些常数k。这有时被称为<一href="http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations">soft-O"并用于环境中对数项是无关的。在这种情况下，你可以说，这两个功能是O（1），虽然这种用法是不是在简单的算法分析常见的（事实上，维基百科之外，我所看到的这种用precisely一次）。

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).

希望这有助于！

这篇关于什么是大O的功能（log n）的^ 2 + LOGN的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！