可以通过非递归算法在n^2时间上解决的问题。相同的问题可以在n lg(n)操作中使用递归算法来解决，将输入分成两个相等的部分，并lg(n)使用操作将两个解决方案组合在一起。你认为哪种算法更有效？
编辑：基本情况：如果 n = 1，则 T(n) = 1。
这意味着nlgn lgn它将比 更有效n^2。对？
问问题
2788 次
1 回答
4
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超过一百万时仍然会更快。
于 2018-10-05T11:58:54.543 回答