Какова сложность запуска цикла дважды из одного и того же входного массива?

Question

Я новичок в алгоритмах, и очень заинтересован в изучении и реализации их.
Изучая их через все доступные онлайн-материалы, которые я могу найти. Я немного запутался по этому поводу -

Рассмотрим этот код -

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

Какова будет сложность этого?
O (n) или O(n^2)?

Answer 1

Предполагая, что { . . . } постоянное время, то сложность одного цикла составляет O (n).

Какова сложность двух "смежных" циклов? Это O(n) + O(n). Или вы можете думать об этом как O(n + n) -> O(2n). Константы выпадают из сложности, так что это O (n).

Это совсем другое дело с вложенными циклами. Итак, следующее:

for (int i=0; i<n; i++) { ..... }
    for (int j=0; j<n; j++) { ..... }

будет О (п ^2).

Answer 2

Сложность останется O (n)

(Предполагая, что у вас нет другого цикла внутри цикла for).

Answer 3

Идея вычисления временной сложности заключается в том, сколько раз ваш цикл / функция выполняет каждый шаг внутри нее?
например: for петля

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

код в фигурных скобках напечатает n раз hello поэтому временная сложность этого цикла будет O(n)

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

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

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

это напечатает hellon^2 время, почему? потому что для каждого внешнего for loop (i) вы выполняете внутреннюю for loop(j)O(n) время. так O(n^2)будет сложность времени

читать дальше http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/