Найти вычислительную сложность для следующих циклов
For n=1 : Inner loop will execute 1 time.
For n=2 : Inner loop will execute 1+2 times.
For n=4 : Inner loop will execute 1+2+4 times.
For n=8 : Inner loop will execute 1+2+4+8 times.
. . .
Как я могу найти вычислительную сложность?
Мой ответ: Число итераций внутреннего цикла = N + (N/2) + (N/4) + (N/8) + ... (н/п)
Общее время сложность Θ (n). Чтобы увидеть это, обратите внимание, что внутренний цикл делает Θ (i) работать на итерацию и что i принимает значения 1, 2, 4, 8, 16, 32, ..., 2 log n. Если суммировать это вверх, используя формулу для суммы геометрической прогрессии, мы получаем
1 + 2 + 4 + 8 + ... + 2 лог п = 2 журнал N + 1 - 1 = 2 & middot; 2 журнал п - 1 = 2n - 1
Так общая работа является Θ (п).
Надеюсь, это поможет!
Спасибо. Но почему 2^logn не n? – ammarx
@ ammarx- Предполагая, что мы используем логарифмы base-2, они идентичны. – templatetypedef
Вы можете официально приступить как следующий, чтобы получить как точное количество команд, которые будут выполнены, а также порядок роста:
Не должна ли она читать 'При п = 1, 2,3,4' вместо 'For n = 1,2,4,8'? И количество выполняемых операций составляет 2^n-1? – halfbit
Я выбираю n = 1,2,4,8 ..., чтобы было легче найти сложность, потому что i = i * 2. Я не знаю! – ammarx