如何确定该算法的平均案例复杂度?

让我们考虑一个相关的问题。想象一下,你有一枚硬币,它以概率p正面朝上翻转。你需要在硬币正面朝上翻转多少次?答案是1/p,因为

• 有一个p的机会,你需要一个翻转。
• 有一个p(1-p)的机会,你需要两个翻转(第一个翻转必须去尾部,第二个必须去头部)。
• 有一个p(1-p)^2的机会,你需要三个翻转(前两个翻转需要到尾部,第三个必须到头部)
• ...
• 有一个p(1-p)^(k-1)的机会,你需要k个翻转(第一个k-1翻转需要走尾,第k个需要走头)

这意味着翻转次数的预期值为

p+2p(1-p)+3p(1-p)^2+4p(1-p)^3+。。。

=p(1(1-p)^0+2(1-p)^1+3(1-p)^2+…)

现在我们需要计算出这个总和是多少。一般形式为

p从k=1到无穷大的和(k(1-p)^k)。

与其求解这个特殊的求和,不如让我们把它变得更一般。设x为某个变量,稍后我们将其设置为1-p,但现在我们将其视为自由值。然后我们可以将上述总和重写为

p从k=1到无穷大的和(kx ^(k-1))。

现在来看一个有趣的技巧:注意这个表达式的内部是x^k对x的导数。因此,这个和是

p从k=1到无穷大的和(d/dx x^k)。

导数是一个线性算子,所以我们可以把它移到前面:

p d/dx和从k=1到无穷大(x^k)

内部和(x+x^2+x^3+…)是1/(1-x)-1的泰勒级数,所以我们可以简化它得到

p d/dx(1/(1-x)-1)

=p/(1-x)^2

由于我们选择了x=1-p,这简化为

p/(1-(1-p))^2

=p/p^2

=1/p

呼!这是一个很长的推导过程。但它表明,所需抛硬币的预期次数为1/p。

现在,在你的例子中,你的算法可以被认为是投掷概率为p的mn硬币,如果其中任何硬币出现了正面,就停止。当然,您需要投掷的预期硬币数量不会超过您被允许无限频繁翻转的情况,因此您的预期运行时间最多为O(1/p)(假设p>0)。

如果我们假设p独立于m和n,那么我们可以注意到,在经过一些初始增长后,随着翻转次数的增加,每个添加到总和中的项都以指数形式低于之前的项。更具体地说,在无穷和的情况下,在近似对数地向和中添加许多项后,很可能会偏离总和。因此,假设mn大致大于Θ(log p),则总和最终为Θ(1/p)。因此,在大O意义上,如果mn独立于p,则运行时为Θ(1/p)。