棋盘算法，快速排序，实验报告 

//快速排序算法 随机生成数（N=10K）： 排序结果： 六、分析思考 // 棋盘覆盖算法 kk设T(k)为覆盖2?2棋盘的时间 由算法的分治策略得算法的时间复杂性递推式为： O(1)k?0?T(k)???4T(k?1)?O(1)k?0 6

解： T(k)?4T(k?1)?O(1)?? ?4kT(0)?O(1)?4i?4kO(1)?O(1)(4k?1)/3i?0k?1 得： T(k)?O(4k) kk 由于覆盖一个2?2棋盘所需L型骨牌个数为 故算法是在渐进意义下最优的解 //快速排序算法 快速排序算法是对冒泡排序算法的一种改进，采用分治策略，步骤如下： 1. 选取一个基准元素（pivot） 2. 比pivot小的放到pivot左边，比pivot大的放到pivot右边 3. 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2 平均情况下快速排序的时间复杂度是O(n\\lgn)，最坏情况是O(n2)。 Ⅰ 当划分成的两个子问题分别包含 n-1 和 0 个元素时 最坏情况发生。划分操作的时间复杂度为O(n) T(0)=O(1) 这时算法运行时间的递归式为 T(n)=T(n?1)+T(0)+O(n)=T(n?1)+O(n) T(n)=O(n2) Ⅱ 当划分产生的两个子问题分别包含?n/2?和?n/2??1个元素时 最好情况发生，此时算法运行时间递归式为 T(n)=2T(n/2)+O(n) T(n)=O(nlgn)

7