Сложность во время выполнения вложенных циклов for - PullRequest
Новая
       60

Сложность во время выполнения вложенных циклов for

0 голосов
/ 12 октября 2018 
for(a = c; a > 0; a/=2) 
    for(b=0; b < 2*a; b++)

Я пришел к выводу, что это O (nlogn) время выполнения, но я не уверен .. Моя логика заключается в том, что самый внешний цикл for выполняет logn раз, поскольку он делится на 2 каждый раз, а затемсамый внутренний цикл for работает в 2 раза вдвое меньше;следовательно, он работает n раз.

1 Ответ

0 голосов
/ 12 октября 2018 
#include <iostream>

int main() {

    int c = 16;

    for(int a = c; a > 0; a/=2) {

        for(int b =0; b < 2*a; b++)
            std::cout << "*";

        std::cout << std::endl;
    }
}

output 

********************************
****************
********
****
**
  • В первом внутреннем цикле вы видите, b от 0 до 2 * a
  • Во втором внутреннем цикле, который вы видите, b изОт 0 до 2 * (a / 2)
  • В третьем внутреннем цикле вы видите, b от 0 до 2 * (a / 4)

сумма этих: 2a + a +a / 2 + ... + 1 = 2a -1 \ in O (n), так как размер ввода.

...