当一开始学习到《概率分析和随机算法》时,一头雾水,这里倒底是想干什么呢?概率在算法里有什么作用?另外为什么要使用随机算法?如果你不熟悉概率论的基本知识,就更会抓狂。由此可见,要学习计算机不懂数学,是不行的。如果想学会算法,不懂数学就更加不行了,在这里无论怎么强调数学的重要性都不为过。有人曾经说过,21世纪的文盲不是不会读书识字,而是不懂数学,现在是人工智能时代、大数据时代,利用数学的机会更多了。
首先来解决第一个问题,就是概率在算法中有什么用。要理解这个,得从一个问题中进行理解,这个问题在书中描述如下:
假如你要雇佣一名新的办公助理。你先前的雇佣尝试都失败了,于是你决定找一个雇佣代理。雇佣代理每天给你推荐一个应聘者。你面试这个人,然后决定是否雇佣他。你必须付给雇佣代理一小笔费用,以便面试应聘者。然而要真的雇佣一个应聘者需要花更多的钱,因为你必须辞掉目前的办公助理,还要付一大笔中介费用给雇佣代理。你承诺在任何时候,都要找最适合的人来担任这项职务。因此,你决定在面试完每个应聘者后,如果该应聘者比目前的办公助理更合适,就会辞掉当前的办公助理,然后聘用新的。你愿意为该策略付费,但希望能够估算该费用会是多少。
把这个问题简化一下,也就是使用数学的语言来总结一下,就是这样:假设面试费用为Ci,雇佣的费用为Ch,假设整个过程中雇佣了m次,于是总的费用是 nCi mCh。由于n是