第1章算法分析的基本概念和方法教学幻灯片.ppt

对于输入数据a[i]=n-i,i=0,1,n-1算法insertion_sort 达到其最坏情形因此 由此可见Tmax(n)= (n2) 1.5. 分析和求解复杂度的方法 根据循环来统计基本操作的次数 利用递归关系来表示基本操作的次数 用平摊的办法来统计基本操作的次数(Amortized Analysis) 一统计算法基本运算的基本方法 1.5. 分析和求解复杂度的方法 [例1] 根据循环来统计