Может кто-нибудь объяснить, как вы анализируете время выполнения этого кода, используя правильные обозначения?

Question

for (int i=1; i<n; i=i*2)
{
    for (int i=0; i<n; i=i+1)
    {
        if (i<1000)
        cout << i << "\n";
    }
}

Я не понимаю, как получается, что вы выражаете циклы в виде суммирования, чтобы найти время выполнения.Как вы определяете границы суммирования?

Answer 1

Просто посмотрите на количество итераций, которые выполняет каждый цикл.Внешний цикл идет от 1 до n , удваивая i каждый раз, поэтому он записывает ₂ n итераций.Внутренний цикл изменяется от 0 до n , добавляя каждый раз 1, поэтому он выполняет n итераций.

Соедините их вместе, и вы получите O ( n *)1016 * log n )