Big O для вложенной серии для петель

Question

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

Например:

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
    }
}

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

Н + Н-2 + Н + Н-2

2N + 2 (N-2)

4N - 4

O (4N - 4)

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

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

Спасибо.

Answer 1

Это O (n)

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

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

Answer 2

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

Answer 3

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