big-o - 棘手的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)。

or arithmetic operations, doesn't matter on what scale, count as basic operations and can be omitted?

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