algorithm - n^2 和 n*lgn*lgn 哪个更有效率？

Question

一个可以用n^2 次的非递归算法解决的问题。同样的问题可以在 n lg(n) 操作中使用递归算法来解决，将输入分成两个相等的部分和 lg(n) 操作来组合两个解决方案在一起。您认为哪种算法更有效？

编辑:基本情况:如果 n = 1，则 T(n) = 1。

这意味着 nlgn lgn 比 n^2 更有效率。对吧？

Answer 1

与“简单”O(n^2) 相比，递归算法需要做多少额外工作？版本。例如，检查 n<32 可能是个好主意。在你的递归实现中使用 O(n^2)在这种情况下的子算法。但是对于足够大 n , O(n*log(n)*log(n))最终会比 O(n^2) 快.

展示增长差异的表格(log 是以 2 为底的对数):
n n^2 n*log(n) n*[log(n)]^2 1000*n*[log(n)]^2
32 1024 160 800 800 000
1024 ~10^6 ~10^4 ~10^5 ~10^8
10^4 ~10^8 ~10^5 ~2*10^6 ~2*10^9
10^5 ~10^10 ~2*10^6 ~3*10^7 ~3*10^10
10^6 ~10^12 ~2*10^7 ~4*10^8 ~4*10^11
所以，基本上，即使你对递归算法的每个“步骤”进行了 1000 倍的操作，当你的 n 时仍然会更快。超过一百万。