Question

int x = 0;
for (int i = n; i >= 3; i--) {
    for (int j = 1; j <= Math.log(i) / Math.log(2); j++) {
        for (int t = 0; t <= n; t += j) {
            x++;
        }
    }
}
System.out.println(x);

Как видите, у меня есть 3 цикла, условия которых зависят друг от друга.

Мой анализ:

Первый цикл : я предполагал, что он будет запускаться (n-2) раз «наихудший» сценарий.
Второй цикл : я предполагал, что он будет работать log(n) раз «наихудший» сценарий.
Третий цикл : я предполагал, что он будет работать (n) раз «наихудший» сценарий.

Итак, я рассчитал, что функция трех циклов будет: (n-2)*(log(n))*(n)=(n^2)*log(n)-(2n)*log(n) = O((n^2)*log(n))

Я не уверен, что мои расчеты верны, пожалуйста, сообщите!

meowgoesthedog · Answer 1 · 20 марта 2019

Необходимо соблюдать осторожность при работе с несколькими вложенными циклами, условия которых зависят друг от друга. Простое умножение их индивидуальных сложностей может привести к неверному результату.

Внутренняя петля

Это выполняется примерно n / j раз. Точное значение floor([n + 1] / j).
Средняя петля

Это выполняется примерно log2(i) раз. Точный диапазон j составляет [0, floor(log2(i))].
Внешняя петля

Это можно изменить, не затрагивая сложность времени, то есть (int i = 3; i <= n; i++)

Объединение вышеперечисленного в сумму:

Математические заметки:

Число, округленное в меньшую сторону, отличается от своего первоначального значения менее чем на 1, т.е.
Суммацией 1 / j является Гармоническая серия , асимптотическое выражение для которой:
приближение Стирлинга : log(n) + log(n-1) + log(n-2) + log(n-3) + ... = O(n log n)