函数的big

本文介绍了函数的big-O是什么(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) 2 )这样的运行时的算法是相当普遍的.具有这种增长率的函数称为 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)2). Functions with this growth rate are called polylogarithmic.

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

By the way, typically (log n)k is written as logk n, so the above algorithm would have runtime O(n log2 n. In your case, the function log2 n + log n would be O(log2 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 (nk) has runtime O(log n), assuming that k is a constant. This is because log (nk) = 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 (nk)) 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) logk 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).

希望这会有所帮助！