对数算法的大哦复杂度

Question

我计算大哦的复杂度时遇到了更多的问题。由于日志库操作，我无法解决两个问题。这里有两个问题：

N =＃数据项被操纵

1）N^3 + N^2日志（基数为2）N + N^3日志（基数为2）N

2）2n^3 + 1000n^2 + log（基数4）n + 300000n

当日志具有基数时，我感到困惑。你如何计算这些复杂性？任何人都在意如何解释如何尽可能详细地解释复杂性？

Answer 1

对数的基数是不相关的。你可以忽略它。因此：

1）它是O(n^3 log n)，因为这是增长最快的术语。

2）出于同样的原因，它是O(n^3)。

由于log base a (x) = log base b (x)/log base b (a)的基数不相关，所以任何对数都与常数不同。

我建议你阅读更多关于对数here的性质。

Answer 2

你并不需要“为基数计算的复杂性”，你可以比较其增长速度到其他条款的（见本graph of logarithm growth rates，给你一个想法）

注意，要解决这些问题，你不需要注意日志的基础。

O(x + y + z) === O(max(x,y,z)) 

因此，决定总结术语中哪一个最大，并且可以解决您的问题。

Answer 3

在计算渐近复杂度时，n被认为非常大，因此可以忽略常数。当你有一笔款项时，只考虑最大的期限。

在你的例子，这导致：

1）N^3的log（n）

2）N^3