Почему временная сложность 2 для циклов не равна O (n * 2 ^ n)?

Question

Временная сложность для этого метода составляет O(2^n) в соответствии с моим проф.

Я чувствую, что временная сложность для этого метода должна быть O(n * 2^n), потому что

Внешнее для l oop стоимость O(n)

внутренний для l oop стоимость O(2^n)

public static int loop(int n) {
    int j = 1;
    for (int i = 0; i < n; i++) {
        for (int k = j; k > 0; k--) {
            System.out.println("Hello world");
        }
        j *= 2;
    }
    return j;
}

Answer 1

Рассмотрим это:

Для i = 0: j = 1 -> 2^0

Для i = 1: j = 2 -> 2^1

Для i = 2: j = 4 -> 2^2

Для i = 3: j = 8 -> 2^3 ....

Для i = n-1: j = 2^n-1

Если добавить все из них:

2^0 + 2^1 + 2^2 +.....+2^(n-1) => order of 2^(n) -> 2^(n) - 1 to be precise

Таким образом, сложность времени составляет O(2^n)

Answer 2

Вы правы, что внешний l oop работает O (n) раз. Вы также правы, что максимальное количество времени, которое внутренний l oop занимает до конечного значения sh, составляет O (2 ⁿ ). Поэтому нельзя ошибочно утверждать, что проделанная работа не более O (n2 ⁿ ).

Однако эта граница не является жесткой, поскольку в этом анализе предполагается, что работа число выполненных на каждой итерации внутренней l oop равно максимальной работе, выполненной внутренней l oop на каждой итерации. Рассуждая по аналогии: если у меня десять животных, и самое тяжелое из них - слон весом 1000 кг, я могу правильно сказать, что животные в совокупности весят не более 10 000 кг, умножая количество животных на максимальную массу, но это может быть диким завышением , Было бы лучше просто сложить массы каждого отдельного животного, чтобы увидеть, что я получу.

В этом случае нам нужно наблюдение, чтобы i-й раз мы go прошли через этот внутренний l * 1034. * мы проводим 2 ⁱ итераций. Это означает, что общая выполненная работа примерно равна

2 ⁰ + 2 ¹ + ... + 2 ^n-1 .

Это сумма геометрии серии c, и она получается до 2 ⁿ - 1, следовательно, общая O (2 ⁿ ) ограниченный по времени. Возвращаясь к примеру с животными, если мои животные - это белка весом 1 кг, черепаха весом 10 кг, человек весом 100 кг и слон весом 1000 кг, то почти вся масса учитывается слоном, потому что массы растут так быстро. Формальное выражение для суммы геометрических рядов c делает эту идею математически строгой.