舍伍德算法思想是通过引入随机化策略将确定性算法改造为随机算法，打破原来确定性算法在某些实例情况下， 其时间复杂性必然远高于平均时间复杂性的规律。下面哪些算法可以应用舍伍德算法思想？
A: 快速排序算法
B: 线性时间选择算法
C: 归并排序
D: 跳跃表
A: 快速排序算法
B: 线性时间选择算法
C: 归并排序
D: 跳跃表
举一反三
- 舍伍德型概率算法是概率算法的一种,下列关于其性质的选项中,错误的是() A: 通过精心设计,舍伍德型概率算法可以改进算法在最坏情况下的时间复杂性。 B: 借助于随机预处理技术,即不改变原有的确定性算法,仅对其输入实例随机排列(洗牌),然后再执行确定性算法。 C: 舍伍德型概率算法是用来消除算法的时间复杂性与不同输入实例之间的运行时间差别。 D: 在确定性算法的某些步骤引入随机因素,将确定性算法改造成舍伍德型概率算法。
- 快速排序算法和线性时间选择算法的随机化版本是（） A: 舍伍德算法 B: 蒙特卡罗算法 C: 拉斯维加斯算法 D: 数值随机化算法
- 快速排序算法，其时间复杂性是[img=46x27]1803a65dc3b3b4a.png[/img]，而其平均时间复杂性是[img=67x25]1803a65dcc81182.png[/img]，下面哪些方法可以改善快速排序算法的性能？ A: 拉斯维加斯算法 B: 蒙特卡洛算法 C: 洗牌算法 D: 舍伍德算法
- 下面说法错误的是（） A: 借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。 B: 随机算法共同点是计算时间越多或运行次数越多,正确性越高 C: 舍伍德算法总是有解, 且解总是正确的，改进了算法的平均性能。 D: 确定性算法求解同一实例用同一算法求解两次，所得结果完全相同。
- 下面属于随机算法的是（） A: 数值随机算法 B: 舍伍德算法 C: 蒙特卡罗算法 D: 拉斯维加斯算法