[工学]快速排序平均情况下的复杂性.doc
《[工学]快速排序平均情况下的复杂性.doc》由会员分享,可在线阅读,更多相关《[工学]快速排序平均情况下的复杂性.doc(3页珍藏版)》请在三一文库上搜索。
设数组中所有元素两两不同,且所有置换出现的可能性是一样的。:数组中待排序的个数只有个时排序所做的复杂性,设分区完成后,设(first, ,splitPoint-1)中没有两个元素互相之间做过比较,因此,子区间各种置换出现的概率还是等可能的。对 (splitPoint+1, ,last),也作同样的假定。 对 (4.1)快速排序在最好情况下的复杂性为定理4.2对递归方程(4.1),使对 ,有成立。因为是单调增函数,所以:所以:令,如,就得到:推论4.3 平均情况下即设所有置换等可能性地出现时快速排序所做的比较的次数为。平均情况下快速排序算法复杂性的精确估算 (4.2) (4.3)n方程(4.2)- (n-1)方程(4.3),得到:所以令:则递归方程化为:因为,调和级数:,其中所以:所以:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工学 快速 排序 平均 情况 复杂性
三一文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
链接地址:https://www.31doc.com/p-1977378.html