递推方程的实例(续) 例3哪种排序算法在最坏情况下复杂度比较低? 插入排序、归并排序 插入排序 W(n)=W(n-1)+n-1 W(1)=0 解得W(n)=On 归并排序,不妨设n=2k W(n)=2W(m/2)+n-1 W(1)=0 解得Wn)=O( nlogn)6 例 3 哪种排序算法在最坏情况下复杂度比较低？ 插入排序、归并排序 插入排序 W(n) = W(n −1) + n −1 W(1) = 0 解得 W(n) = O(n2). 归并排序，不妨设 n = 2k. W(n) = 2W(n/2) + n－1 W(1) = 0 解得 W(n) = O(nlogn) 递推方程的实例（续）