棘手的 Big-O 复杂度

Question

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();
    }
}

我认为复杂度应该是O(logn)。由于内部循环的影响，外部循环最多只会执行100次，因此可以省略它。

我不确定的是while子句是否应该纳入大O复杂度中？对于非常大的i值，它可能会产生影响，或者算术运算，无论在什么规模上，都可以视为基本操作并省略。

- George Kagan

---

标记为作业并诚实，点赞！ - Aiden Bell

while循环计数 - 它是O(log m) - President James K. Polk

Answer 1

while循环的时间复杂度是O(log m)，因为你不断地将m除以3，直到它小于或等于100。

由于在这种情况下，100是一个常数，所以可以忽略它。

内部循环的时间复杂度是O(log n)，因为你将j乘以2，直到它超过n。

因此总的时间复杂度为O(log n + log m)。

算术运算是否可以忽略？不论在什么规模下，都算作基本操作并可以省略吗？

算术运算通常可以被省略，但也要取决于编程语言。这看起来像Java，并且看起来你正在使用原始类型。在这种情况下，考虑算术运算为O(1)是可以的。但如果你使用大整数，那么加法和乘法就不再是O(1)了。

- IVlad

---

@Sekhat: 同意，我也给了他+1 :) - President James K. Polk

Answer 2

该复杂度为O(log m + log n)。

while循环执行log3(m)次 - 一个常数 (log3(100))。外部for循环执行一定数量的次数(大约100次)，内部循环执行log2(n)次。

- President James K. Polk

Answer 3

这个while循环将m的值除以3，因此这样的操作次数将是log（3为底）m

对于for循环，您可以将操作次数视为2个求和 -

求和（k = 0到i）[求和（j = 0到lg n）（1）] 求和（k = 0到i）[lg n + 1] (lg n + 1)（i + 1）将是总操作次数，其中log项占主导地位。

这就是为什么复杂度为O（log（3为底）m + lg n） 这里的lg是指以2为底的对数

- Chaitra Suresh

---

请问您能否解释一下为什么要加上 O(log (base3) m + lg n)，而不是相乘呢？ - Sunny Gupta

根据我的看法，应该是 log（底数为3）m + （log（底数为3）m * lg n）。 - Sunny Gupta