Я застрял со сложностью времени

Question

Я изучаю временную сложность алгоритмов и застрял в чем-то. Можете ли вы помочь мне найти временную сложность приведенного ниже кода? Спасибо.

x=1;
for(i=0; i<=n-1; i++){
        for(int j=1; j<=x; j++)
            std::cout<<j<< std::endl;
        x =x*2;
    }

Answer 1

Вот пошаговое руководство по моему мыслительному процессу:

1. Первый цикл for запускается n раз, поэтому сложность времени составляет O (n) .
2. Второй цикл for увеличивается вдвое по мере увеличения числа циклов по мере продвижения первого цикла for, поэтому сложность по времени составляет O (2 ^ n) .
3. Объединениево-вторых, похоже, что код имеет временную сложность O (n * 2 ^ n) .
4. Однако, если подумать глубже, это неверно.
5. ЕслиВы учитываете количество циклов, которые запускает второй цикл for, это 1, 2, 4, 8, ..., 2 ^ (n-2), 2 ^ (n-1).
6. Таким образомобщее число циклов будет равно 2 ^ (n-1) + 2 ^ (n-2) + ... + 2 ^ 1 + 2 ^ 0.
7. для любого заданного x, x + x/ 2 + x / 4 + ... + 2 + 1 = 2 * x - k (где значение k зависит).
8. При применении той же концепции общее число циклов составляет 2 * 2 ^ (n-1).
9. В результате общая сложность времени составляет O (2 ^ n) .