棘手的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子句,它是否应该被整合到Big-O复杂性中？对于非常大的i值,它可能产生影响,或算术运算,无关紧要,算作基本操作,可以省略？

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).

Answer 2

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

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