什么是随机算法

用骰子来选

有的解法靠掷骰子决定下一步做什么。不是想好了再选，而是干脆交给运气。
每按一次按钮，骰子就滚一次。
会掷出几点，事先谁也不知道。

一按，骰子就滚起来。下一次掷出几点，事先没法知道。

为什么要故意交给运气？要是总用同一种方式来选，就可能有人盯住这个习惯，专门造出难对付的输入。
随机地选，就能躲开这种算计。
真正的用处，下一步就能看到。

用随机的基准

快速的排序里，有一种是先定一个基准，比它小的放左边，比它大的放右边。
可要是总拿最后一个值当基准，遇到已经排好队的输入，每次都切得一边倒，就会非常慢。

比一比总拿最后一个值当基准 vs 随机基准，各要切几次。（一边倒 = 慢）

随机选基准，不管来什么输入，几乎都不会一边倒，专门针对坏输入的陷阱也不管用了。
所以平均来看，每次都切得比较均匀，排序就快了。

多掷几次来估算

随机还能用来估算。在正方形里画一个四分之一圆，也就是把圆分成四份中的一份，再往里面乱撒点。
看落在四分之一圆里的点占全部点的多少，就能估算出它占了多大面积。
一个个地撒点看看。

点撒得越多，比例就越接近真值。（圆内的点 / 全部的点）

点少的时候，估算忽高忽低。可点撒得越多，比例就越紧贴真值。
一两次的运气靠不住，可掷过无数次的平均值是靠得住的。
这就是多掷几次来估算答案的办法。

拿确定换速度

随机解法不是白来的。又快又简单，代价是不能保证每次答案都一样，运气不好时偶尔也会慢。
点开两边，比一比得到什么、付出什么。

点一点得到的和付出的，比一比。（快·简单 vs 不能保证同样的答案）

所以随机并不总是好的，它有自己合适的位置。
当又快又简单比一点点不确定更值钱时，就用它。付出一点确定，换来速度和简单。

一眼看总结

把随机解法一眼看下来：用骰子来选，用随机基准躲开陷阱，多掷几次来估算答案，拿确定换速度。
按顺序点开要点，自己总结一下。

按顺序点这四个要点来总结。（骰子 · 随机基准 · 多掷估算 · 交换）

说是交给运气，听着有点马虎，可用得好的话，随机是又快又靠得住的工具。
数据越是多得惊人，多掷几次来估算的这个想法就越派得上大用场。
下一课，我们走进由点和线连起来的世界：图。