Сложная сложность 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) раз.

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 (base3) m + lg n) Здесь LG относится к журналу базы 2