随机算法：很难？那不妨用英雄联盟这款游戏带你弄懂吧

相信大家熟知英雄联盟这款游戏吧，像神一般的男人Uzi，厂长这些的退役多少都会让人觉得爷青结。但是那都是没办法的事情，毕竟电竞都是靠吃年龄饭的。而今天就是想让大家从英雄联盟这款火爆全球的游戏暴击几率为例，了解随机算法。

从英雄联盟这款游戏来说，它第一没有闪避。再从暴击方面来说，其实你看为什么我们都说，ADC在追求百分百暴击。就官方一直尽量在规避那些随机性的东西。而且其实英雄联盟的暴击是伪随机的。他是有补偿机制的。

你知道真随机和伪随机的概念吗？真随机就是比如说你10%的暴击几率，你每一下就是10%，但是伪随机就是10%第一下没出现暴击，第二下会比10%高。你的每一次没出现暴击就会让你下一次出现的概率更高。也就是说你最起码在真随机的状态下，你如果脸黑一些。你可能这一整局游戏都不会出现暴击。

而官方的回答就是做不出来真随机的算法，最起码真随机算法在游戏里是做不出来的。就像你可能使用basic编程都能做到百分百的准确，但是在游戏里，这是不存在的。也许这是游戏引擎的问题吧。好了，别的不多说，让我为你介绍一下随机算法。

问题：给定一个n个数字且ε> 0的未排序数组A []，请计算其秩（在已排序A []中的位置）在[（1-ε）n / 2，（1 +ε）范围内的元素n / 2]。对于½近似中值算法＆epsilom; 是1/2 =>等级应在[n / 4，3n / 4]范围内。我们可以在O（n）预期时间和O（n）最短时间中找到第k个最小元素。

如果我们希望在不到O（n）的时间内允许较低的可能误差怎么办？以下步骤表示一种算法，该算法的执行时间为O（（Log n）x（Log Log n））次，并以不大于2 / n 2的概率产生不正确的结果。

1.从数组中随机选择k个元素，其中k = c log n（c是一个常数）

2.然后插入一组。

3.对集合的元素进行排序。

4.返回集合的中值，即集合中的第（k / 2）个元素

以C语言为例：

时间复杂度：我们使用C ++中STL提供的集合。在STL集中，每个元素的插入花费O（log k）。因此，对于k次插入，花费的时间为O（k log k）。现在用c log n=> O（c log n（log（clog n）））=> O（log n（log log n））替换k错误概率如何小于2 / n 2？如果集合S至少有k / 2个元素来自左四分之一或右四分之一，则算法会出错。

可视化此语句很容易，因为我们报告的中位数将是第（k / 2）个元素，如果我们从左四分之一（或右四分之一）中取k / 2个元素，则中位数将是左四分之一（或正确的季度）。数组可分为大小为n / 4的四个四分之一。

因此，P（选择左四分之一）为1/4。那么，至少k / 2个元素来自左四分之一或右四分之一的概率是多少？此概率问题与以下相同：给定一个硬币，使HEADS的概率为1/4，而TAILS的概率为3/4。硬币被扔了k次。我们至少得到k / 2个HEADS小于或等于的概率是多少？说明：如果将k = c log n设为c = 10，我们得到  P <=（1/2）2 log n  P <=（1/2）log n 2  P <= n -2

从左四分之一 选择至少k / 2个元素的概率<= 1 / n 2从左或右四分之一选择至少k / 2个元素的概率<= 2 / n 2因此，算法产生的错误结果的概率小于或等于2 / n 2。