6 
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 子句，是否应该将其合并到 Big-O 复杂性中？对于非常大的i值，它可能会产生影响，或者算术运算，无论规模多大，都算作基本运算并且可以省略？

4

3 回答 3

11

while循环是因为O(log m)你一直除以m直到3它低于或等于100。

由于 100 在您的情况下是一个常数，因此可以忽略它，是的。

内循环O(log n)就像你说的那样，因为你乘以j直到2它超过n.

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

或算术运算，无论在什么规模上，都算作基本运算并且可以省略？

算术运算通常可以省略，是的。但是，这也取决于语言。这看起来像 Java，看起来您正在使用原始类型。在这种情况下，可以考虑算术运算O(1)，是的。但是，例如，如果您使用大整数，那真的不行了，因为加法和乘法不再是O(1).

于 2010-06-06T13:00:00.870 回答
5

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

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

于 2010-06-06T12:57:40.423 回答
2

while 循环将 m 的值除以 3，因此此类操作的数量将为 log(base 3) m

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

summation (k = 0 to i) [ summation (j = 0 to lg n) (1)] summation (k = 0 to i) [lg n + 1] (lg n + 1) ( i + 1) 将是总计操作数，其中日志项占主导地位。

这就是为什么复杂度是 O(log (base3) m + lg n) 这里 lg 是指 log to base 2

于 2013-01-25T09:30:36.127 回答