数据结构 第三部分.ppt

* 所以T(N) = cNlogN + N = o(NlogN) * 平均情况 考虑了每个可能的子集规模的开销并对它们求平均值由于有两个递归调用加上用来执行划分的线性时间我们得到 对等式两边乘以N得 * NT(N) = 2(T(0) + T(1) + T(2) ++ T(N-1) + cN2 然后对N-1的情况套用等式 得 (N-1)T(N-1) = 2(T(0)+T(1)+T(2)+ +T(N-