问题:
[填空题]
快速排序算法选取轴点时可以采取不同的策略,本题试图用实例说明“三者取中”的策略比随机选取的策略倾向于得到更平衡的轴点
设待排序序列的长度n很大,若轴点的选取使得分割后长/短子序列的长度比大于9:1,则称为不平衡
针对不同的轴点选取策略,估计其发生不平衡的概率(请填十进制小数):
从n个元素中等概率随机选取一个作为轴点:____
从n个元素中等概率选取三个元素,以它们的中间元素作为轴点:____
快速排序算法选取轴点时可以采取不同的策略,本题试图用实例说明“三者取中”的策略比随机选取的策略倾向于得到更平衡的轴点
设待排序序列的长度n很大,若轴点的选取使得分割后长/短子序列的长度比大于9:1,则称为不平衡
针对不同的轴点选取策略,估计其发生不平衡的概率(请填十进制小数):
从n个元素中等概率随机选取一个作为轴点:____
从n个元素中等概率选取三个元素,以它们的中间元素作为轴点:____
Copyright © 2024 www.daanwo.com All Rights Reserved |