Ожидаемая временная сложность O (n ^ 2), но это приводит к O (n). Кто-нибудь может объяснить почему?

Question

Какой должна быть временная сложность следующего кода? Я попытался подумать и придумать O (n ² ), но вывод говорит, что он имеет O (n). Может кто-нибудь объяснить, пожалуйста, через код?

for(int i = 0; i < n; i++){
    for(; i < n; i++){
        cout << i << endl;
    }
}

Answer 1

Сложность вашего кода O (n).

Почему?

Потому что, хотя вы написали два цикла for, что, вероятно, заставило вас задуматься сложность O (n ² ), ваш код фактически равен единице для l oop, например:

for (i = 0; i < n; i++){
    std::cout << i << std::endl;
}

Как только внутреннее для l oop заканчивается, i равно n и, следовательно, условие внешнего для l oop i < n больше не выполняется.

Answer 2

Следует отметить, что при использовании таких циклов for вы используете одну переменную.

Независимо от того, сколько внешних циклов вы добавите, ваш код будет одинаковым с условием i<n, преобладающим во всех. Самый внутренний l oop - это тот, который будет работать до i=n-1, остальное просто не будет удовлетворять условию.

for(int i=0; i<n; i++)
{ for(; i<n; i++)
  { for(; i<n; i++)
    { for(; i<n; i++) // and so on.
       std::cout<<i<<"\n";
    }
  }
}

Предоставление варианта этому, если вы будете наблюдать один В таком случае сложности O (n ² ) ваше состояние было бы i<n*n:

for(int i=0; i<n; i++)
{ for(; i<n*n; i++)
    std::cout<<i<<"\n";
}

Answer 3

Временная сложность вашего кода равна O(n), а не O(n^2), потому что когда внутренний l oop заканчивается, в это время значение i уже достигло n. Поэтому внешний l oop больше не может работать.

for(int i = 0; i < 2; i++){
    for(; i < 2; i++){
        cout << i << endl;
    }
   //after loop run two times i has value 2.
   //and outer loop cannot run anymore
}