算法的复杂度

Question

我正在备考考试，看到了这个问题，所以我做了以下事情，是否正确？

while循环的时间复杂度为O(log3n)。

for循环的时间复杂度约为O((n-(某些数学))*log2n)，因为有线性的减号，所以我认为整个方法的时间复杂度为O(nlogn)，除非我错了，应该是类似于

O((n-(n/log3n))*log2n) <- 不完全相同但相似，真的搞不清楚。

这里的减号是线性的还是非线性的？如果不是线性的，那么正确的大O是什么？

public void foo (int n, int m)
{
    int i = m;
    while (i>100)
     i = i/3;
    for (int k=i; k>=0; k--)
    {
        for (int j=1; j<n; j*=2)
         System.out.print(k + "\t" + j);
        System.out.println();
    }
}

- Seth Keno

---

你为什么关心这个负号？括号内的表达式先验地不能小于零，因此第一项大于等于第二项，因此你可以使用渐近地趋向于O(nlogn)的第一项。除非你在计算时出错了：O((n-(n/log3n))*log2n) - mangusta

Answer 1

while循环的运行时间为O(logm)。

当while循环结束时，i小于等于100，因此下一个for循环最多运行100次。

内部循环将在外部循环的每次迭代中运行O(logn)次。因此总时间为O(logm + 100*logn) = O(logm + logn)。

- fgb

---

请问您能否解释一下为什么它不是O((n/(n/100))*logn)？m/(m/100)将会在每个m > 100的情况下给我100（这是最坏的情况），而我正在循环m/(m/100)次，每次循环都要进行log2n次操作。 - Seth Keno

我觉得我回答了自己的问题...如果对于所有m>100，m/(m/100)始终是100，那么我基本上是在说bigO是O(100*logn)，这是O(logn)，我能否从你写的bigO中减去logn（因为log2n比log3m大），并将其简化为O(log3m)？ - Seth Keno

@SethKeno 第一个循环运行的次数取决于m。对于m>100，它并不总是100。我不明白你为什么要除以m。增加m会增加总时间，因为第一个循环所以必须在最终表达式中。 - fgb

Answer 2

第一个while循环的运行时间为O(100*log_3(m))。这应该很容易理解。

对于外层的for循环，请注意i的最大值为100（由于前面的while循环），而内部循环的复杂度为O(100*log_2(n))，因此整体渐进上限为O(log_3(m) + log_2(n))。

- Filipe Gonçalves

---

在大O符号表示法中指示日志的底数是多余的。 - Bernhard Barker

@Dukeling 我知道。只是为了让提问者更清楚地看到它的来源，从而使数学更清晰。但还是谢谢您的反馈。 - Filipe Gonçalves