对数算法的 Big-oh 复杂度
我在计算 Big-oh 复杂度时遇到的问题很少。由于日志库操作，有两个问题我无法解决。这里有两个问题：
n = 正在操作的数据项数量
1) n^3 + n^2 log (base 2) n + n^3 log (base 2) n
2) 2n^3 + 1000n^2 + log (base 4) n + 300000n
当日志有基数时我很困惑。您如何计算这些的复杂性？如果可能的话，有人愿意解释一下如何用一些细节来解释复杂性吗？
Few more problems I ran into calculating the Big-oh complexity. There are 2 problems which I cannot solve due to log base operations. Here are the two problems:
n = # of data items being manipulated
1) n^3 + n^2 log (base 2) n + n^3 log (base 2) n
2) 2n^3 + 1000n^2 + log (base 4) n + 300000n
I am confused when the logs have a base number. How do you go about calculating the complexity for these? Anyone care to explain how you get the complexity with a bit of detail if possible?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对数的底是无关紧要的。你可以忽略它。因此：
1) 它是
O(n^3 log n)，因为这是增长最快的项。2) 出于同样的原因，它是
O(n^3)。底数是无关紧要的，因为
对数底数 a (x) = 对数底数 b (x) / 对数底数 b (a)，因此任何对数都与另一个对数相差一个常数。我建议您在此处阅读有关对数属性的更多信息。
The base of the logarithm is irrelevant. You can just ignore it. Therefore:
1) It's
O(n^3 log n)because that's the term that grows the fastest.2) It's
O(n^3)for the same reason.The base is irrelevant because
log base a (x) = log base b (x) / log base b (a), so any logarithm differs from another by a constant.I suggest you read more about the properties of the logarithm here.
您不需要“计算基数的复杂性”，只需将其增长率与其他项的增长率进行比较（请参阅此对数增长率图，给您一个想法）
请注意，要解决这些问题，您不需要关注对数的基数。
因此，决定哪一项的总和最大，您就可以解决您的问题。
You don't need to "calculate complexity for a base number", you can just compare its growth rate to that of the other terms (see this graph of logarithm growth rates, to give you an idea )
Note that to solve these problems, you don't need to pay attention to the base of the logs.
So, decide which of the summed terms is largest and you can solve your problems.
在渐进复杂度的计算中，假设n非常大，因此可以忽略常数。当你有一个总和时，只考虑最大的项。
在您的示例中，这会导致：
1) n^3 log(n)
2) n^3
In the calculation of asymptotic complexity, n is assumed to be very large and thus constants can be ignored. When you have a sum, only take into account the biggest term.
In your examples, this results in:
1) n^3 log(n)
2) n^3