如何从T(n)= 2T(n/2)+ O(n)得到O(nlogn)

从 T(n) = 2T(n/2) + O(n) 可以得到 O(nlogn)。

首先，我们需要了解主定理（Master Theorem），它是解决递归式时间复杂度问题的一个重要工具。主定理的适用条件是：

1. 递归式为 T(n) = aT(n/b) + O(n^d)，其中 a > 0, b > 1, d >= 0。
2. a >= 1 且 b^d >= a。

在这个问题中，我们的递归式 T(n) = 2T(n/2) + O(n) 可以转化为 T(n) = aT(n/b) + O(n^d)，其中 a = 2, b = 2, d = 1。因此，我们可以应用主定理来解决这个问题。

根据主定理，我们可以得到以下三种情况：

1. 如果 a < b^d，则 T(n) = O(n^d)。
2. 如果 a = b^d，则 T(n) = O(n^d * log n)。
3. 如果 a > b^d，则 T(n) = O(n^(log_b a))。

在这个问题中，我们的递归式 T(n) = 2T(n/2) + O(n) 属于第二种情况，即 a = b^d。因此，我们可以得到 T(n) = O(n * log n)。

这个结论表明，从 T(n) = 2T(n/2) + O(n) 可以得到 O(nlogn)。