算法面试题：随机化与概率

1. 什么是随机化算法？

• 使用随机数影响执行过程。
• 结果可能具有随机性。
• 常见于近似算法和抽样。

2. 随机算法的类型有哪些？

• Las Vegas 算法：结果正确但耗时随机。
• Monte Carlo 算法：耗时确定但结果可能有概率错误。

3. 常见概率分析题型有哪些？

• 随机抽样。
• 泊松分布和二项分布。
• 期望值和方差计算。

4. 面试常问的经典题有哪些？

• 随机洗牌（Fisher-Yates）。
• 选择中位数的随机化算法。
• 随机化哈希。

5. 如何评价随机化算法的性能？

• 期望时间复杂度。
• 失败概率。
• 结果稳定性。

6. 什么时候适合使用随机化方法？

• 平衡最坏情况和平均情况。
• 需要快速近似结果。
• 数据规模非常大时。