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/n)
Общая временная сложность равна (n). Чтобы увидеть это, обратите внимание, что внутренний цикл (i) работает на итерации и что i принимает значения 1, 2, 4, 8, 16, 32, ..., 2log n . Если суммировать это, используя формулу суммы геометрического ряда, то получим
1 + 2 + 4 + 8 + ... + 2log n = 2log n + 1 - 1 = 2 2log n - 1 = 2n - 1
Таким образом, общая проделанная работа равна (n).
Надеюсь это поможет!
Вы можете формально действовать следующим образом, чтобы получить как точное количество инструкций, которые будут выполняться, так и порядок роста:
For n=1,2,3,4вместоFor n=1,2,4,8? И тогда количество выполненных операций равно 2 ^ n-1? - person halfbit schedule 08.11.2013