舍伍德型概率算法是概率算法的一种,下列关于其性质的选项中,错误的是()
A: 通过精心设计,舍伍德型概率算法可以改进算法在最坏情况下的时间复杂性。
B: 借助于随机预处理技术,即不改变原有的确定性算法,仅对其输入实例随机排列(洗牌),然后再执行确定性算法。
C: 舍伍德型概率算法是用来消除算法的时间复杂性与不同输入实例之间的运行时间差别。
D: 在确定性算法的某些步骤引入随机因素,将确定性算法改造成舍伍德型概率算法。
A: 通过精心设计,舍伍德型概率算法可以改进算法在最坏情况下的时间复杂性。
B: 借助于随机预处理技术,即不改变原有的确定性算法,仅对其输入实例随机排列(洗牌),然后再执行确定性算法。
C: 舍伍德型概率算法是用来消除算法的时间复杂性与不同输入实例之间的运行时间差别。
D: 在确定性算法的某些步骤引入随机因素,将确定性算法改造成舍伍德型概率算法。
A
举一反三
- 舍伍德算法思想是通过引入随机化策略将确定性算法改造为随机算法，打破原来确定性算法在某些实例情况下， 其时间复杂性必然远高于平均时间复杂性的规律。下面哪些算法可以应用舍伍德算法思想？ A: 快速排序算法 B: 线性时间选择算法 C: 归并排序 D: 跳跃表
- 借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。
- 下面说法错误的是（） A: 借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。 B: 随机算法共同点是计算时间越多或运行次数越多,正确性越高 C: 舍伍德算法总是有解, 且解总是正确的，改进了算法的平均性能。 D: 确定性算法求解同一实例用同一算法求解两次，所得结果完全相同。
- 舍伍德（Sherwood）算法是一种常用的（）算法。 A: 确定性 B: 近似 C: 概率 D: 加密
- 舍伍德算法是概率算法的一种。（)
内容
- 0
概率算法有数值概率算法、舍伍德算法和（）、（）。
- 1
下列随机算法中运行时有时候成功有时候失败的是（） A: 数值概率算法 B: 舍伍德算法 C: 拉斯维加斯算法 D: 蒙特卡罗算法
- 2
舍伍德算法是（）的一种。 A: 分支界限算法 B: 概率算法 C: 贪心算法 D: 回溯算法
- 3
肯定获得可行解，但不一定是正确解的算法是（）。 A: 蒙特卡罗算法 B: 拉斯维加斯算法舍伍德算法 C: 舍伍德算法 D: 数值随机算法
- 4
下列随机算法中运行时,有时候成功有时候失败,有时候正确有时候错误的有（ ） A: 数值概率算法 B: 舍伍德算法 C: 拉斯维加斯算法 D: 蒙特卡罗算法