Сложность вложенного цикла for
Какова будет временная сложность этого следующего блока кода? функция void (int n).
Моя попытка заключалась в том, чтобы внешний цикл выполнялся n / 2 раз, а два внутренних - 2 ^ q раз. Затем я приравнял 2 ^ q к n и получил q как 1/2 (log n) с основанием 2. Умножая временные сложности, я получаю свое значение как O (nlog (n)), а ответ - O (nlog ^ 2 (n )).
void function(int n) {
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; j = 2 * j)
for (int k=1; k<=n; k = k * 2)
count++;
}
Я имел в виду произвольную константу, такую как Q, поскольку нет связи между j, k и n, поэтому вы не знаете, сколько раз она будет выполняться
Ответы 3
Первый цикл занимает: n / 2
Второй цикл: журнал (n)
Третий цикл: журнал (n)
Обратите внимание: поскольку шаг внутренних циклов умножается на два, их соответствующие счетчики экспоненциально растут, достигая n в log(n) с точки зрения временной сложности.
Затем также обратите внимание, что в этом случае константы, такие как 1/2, можно безопасно игнорировать, что приводит к O(n * log(n) *log(n)), таким образом:
O(nlog2n)
Как я пропустил этот @templatetypedef? Может быть, я слишком взволнован, чтобы набрать 50 тысяч репутации! :) Большое Вам спасибо! Ответ обновлен, и теперь я вижу, что вы тоже отправили хороший ответ: +1.
Пора применить золотое правило понимания гнезд петель:
When in doubt, work inside out!
Начнем с исходного гнезда петель:
for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; j = 2 * j)
for (int k=1; k<=n; k = k * 2)
count++;
Этот внутренний цикл будет выполняться Θ (log n) раз, поскольку после m итераций цикла мы видим, что k = 2m, и останавливаемся, когда k ≥ n = 2lg n. Итак, давайте заменим этот внутренний цикл более простым выражением:
for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; j = 2 * j)
do Theta(log n) work;
Теперь посмотрим на самый внутренний оставшийся цикл. Используя те же рассуждения, что и раньше, мы видим, что этот цикл также выполняется Θ (log n) раз. Поскольку мы выполняем Θ (log n) итераций, каждая из которых выполняет Θ (log n) работы, мы видим, что этот цикл можно заменить на более простой:
for (int i=n/2; i<=n; i++)
do Theta(log^2 n) work;
А здесь этот внешний цикл выполняется Θ (n) раз, поэтому общее время выполнения составляет (n log2 n).
Я думаю, что, основываясь на том, что вы сказали в своем вопросе, у вас было правильное понимание, но вы просто забыли умножить на две копии члена журнала, по одной для каждого из двух внутренних циклов.
В вашем коде есть вложенные циклы 3.
- Первый цикл запускает
n/2раза, что почти эквивалентно n при вычислении сложности. - Второй цикл запускает
lognраза. - Третий цикл запускает
lognраза.
Итак, наконец, временная сложность будет O( n * logn * logn ) == O(nlog^2n).
Теперь можно задаться вопросом, как логаризуется сложность времени выполнения двух внутренних циклов. Это можно обобщить следующим образом:
Поскольку мы умножаем на 2 на каждой итерации, нам нужно значение q такое, что: n = 2 ^ q.
Взяв с двух сторон бревенчатую базу 2,
log2 n = log2 (2^q) log2 n = q log2(2) log2 n = q * 1 [ since, log2(2) is 1 ]
Итак, q невероятно похож на logn.
.
Итак, общая временная сложность: O(n*log^2n).
Как получить
2^k?kдаже не вход.