一个可以用非递归算法在n^2时间内解决的问题。同样的问题可以在n lg(n)运算中使用递归算法来解决，将输入分成两个相等的部分，lg(n)运算来组合 两种解决方案结合在一起。您认为哪种算法更有效？
编辑：基本情况：如果n = 1，则T(n(= 1。
这意味着nlgn lgn将比n^2更有效率。右？
与"简单"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超过 100 万时，结果仍然更快。