algorithm - 以下算法的时间复杂度

Question

以下算法的时间复杂度是多少，我怎样才能在我的代码中找到最好和最坏的情况:

boolean b = true;
integer rn = 0;
for(int i=1; i<=n; i++)
{
    for(int j=1; j<=m; j++)
    {
        rn = Math.Random() // random number between j and m 
        if(j%rn==0) b = false;
        while(b)
        {
            for(int k=1; k<=o; k++)
            {
                for(int l=1; l<=p; l++)
                {
                    //some stuff
                    rn = Math.Random() // random number between l and p
                    if(l%rn==0) b=false;
                }
            }
        }
        b = true;
    }
}

前两个 for 循环将始终运行，所以我想这是最好的情况，但我如何衡量这里的最坏情况？

Answer 1

假设rn在[j, m]包含中，则有m - j + 1这个范围内的数字；使用基本的模逻辑，有 floor((m - j + 1)/j) 满足 if 条件。采用概率方法并假设 Random() 是均匀的，总时间复杂度由下式给出:

其中 P(m,j) 是满足 if 条件的概率 - 即 while 循环不执行的概率，S(o ,p) 是 while 循环的时间复杂度。由于内部循环独立于 i, j，我们可以将它们分开处理。

虽然最初看起来内部循环需要类似的分析，但有两个关键区别需要注意:

• b 在 while 循环之前永远不会重置为 true。
• if 条件不会导致任何循环中断。
• 但最重要的是，到两个 for 循环中断时，b 将始终为假。为什么？因为当 l = p 时，rn 唯一可能取的值也是 p； p % p = 0 所以 b 将始终设置为 false(如果尚未设置的话)。

因此内部 while 循环最多只执行一次，S(o,p) = O(op) 很简单。结合这两个结果，我们得到:

对 1 求和可以得到 O(mnop)，但是 P(m,j) 呢？利用向下舍入的数字与其原始值相差小于 1 的事实:

在步骤 (1) 中我们进行了索引移位变换，在步骤 (2) 中使用渐近 Harmonic series summation .由于概率分析中的这个对数项被之前的“批量”项所掩盖:

O(mnop) is therefore both the average and worst case complexity.