Big O для вложенных рядов для циклов

Question

У меня вопрос о вычислении времени работы Big O для серии циклов, которые вложены во внешний цикл.

Например:

 

for (50,000 times) 
{ 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
} 
 

Внешний цикл является постоянной, поэтому считаю, что игнорируется. Неужели так легко сделать следующий расчет?

N + N-2 + N + N-2

2N + 2 (Н-2)

4N - 4

O (4N - 4)

O (4N) - после удаления константы -4

Это правильно?

Спасибо.

Answer 1

Это O (п)

(вы заинтересованы только в том, что это «самый большой» часть уравнения, и вы раздеться константа).

Если у вас цикл я от 1..N и еще один цикл внутри J из i..n, было бы O (N^2).

Answer 2

Это правильно. Вы просто добавляете четыре петли, которые составляют O(N). Таким образом, это 4O(N), то умножается на 50, 000, который является большим числом, но это не N зависит.

Answer 3

Это O (N). Но в этом контексте, в зависимости от того, что у вас есть для N, константа может сильно повлиять на производительность вашего алгоритма.