Какова временная сложность следующих зависимых циклов?

Question

У меня есть вопрос, на который нужно ответить перед экзаменом, который я должен провести на этой неделе.

i = 1;
while (i <= n)
{
    for (j = 1; j < i; j++)
        printf("*");
    j *= 2;
    i *= 3;
}

У меня есть эти зависимые циклы, я вычислил большой O внешнего цикла как O(logn).

Внутренний цикл переходит от 1 до i - 1 для каждой итерации внешнего цикла, проблема, с которой я сталкиваюсь, заключается в том, что я не знаю, как рассчитать сложность времени внутреннего цикла, а затемобщая сложность (я привык просто умножать обе сложности, но я не уверен в этом)

Большое спасибо!

PS: я знаю, что j *= 2 не делаетвлияет на цикл for.

Answer 1

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

Можно задать вопрос о том, сколько раз выполняется тело внутреннего цикла как функция n . На первой итерации внешнего цикла i равен 1, поэтому j никогда не меньше i , поэтому итераций внутреннего цикла нет. Далее i равно 3, поэтому есть две итерации внутреннего цикла, затем восемь в следующий раз, затем коротко 26 ..., 3 ^{i -1} - 1 итерация внутреннего цикла. Вам нужно сложить их все, чтобы вычислить общую сложность.

Хорошо, эта сумма составляет & # x3a3; _{i = 1, этаж (log n )} (3 ^{i -1} - 1), так что вы можете сказать, что сложность гнезда цикла равна

O (& # x3a3; _{i = 1, этаж (log n )} (3 ^{i -1} - 1))

, но такой ответ вряд ли даст вам полную оценку.

Мы можем упростить это, заметив, что наша сумма ограничена связанной:

= O (& # x3a3; _{i = 1, этаж (log n )} (3 ^{i - 1} ))

. На этом этапе (если не раньше) было бы полезно распознать образец суммы сил в нем. Часто полезно знать, что 2 ⁰ + 2 ¹ + ... 2 ^{k - 1} = 2 ^k - 1. Это тесно связано с числовыми представлениями base-2, и аналогичная формула может быть написана для любой другой базы натуральных чисел. Например, для базы 3 это 2 * 3 ⁰ + 2 * 3 ¹ + ... 2 * 3 ^{k - 1} = 3 ^k - 1. Этого может быть достаточно для интуитивного ответа: общее количество итераций внутреннего цикла ограничено константой, кратной числу итераций внутреннего цикла на последней итерации внешнего цикла. который в свою очередь ограничен n .

Но если вы хотите доказать это, то вы можете заметить, что сумма в предыдущем связанном выражении сама ограничена связанным определенным интегралом:

= O (& # x222b; ₀ ^{log n} 3 ⁱ d i )

... и , что имеет решение в закрытой форме:

= O ((3 ^{log n} - 3 ⁰ ) / log 3)

, который явно имеет более простую границу

= O (3 ^{log n} )

. Экспоненты логарифмов сводятся к линейным функциям аргумента логарифма. Поскольку нам нужна только асимптотическая граница, нас не волнуют детали, и поэтому мы можем перейти прямо к

= O (n)