嵌套系列for循环的大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
    }
}

外循环是常量,所以我认为这是被忽略的.那么就像进行以下计算一样简单吗？

N + N-2 + N + N-2

2N + 2(N-2)

4N - 4

O(4N - 4)

O(4N) - 去除-4常数后

它是否正确？

谢谢.

Answer 1

这是O(n)

(你只关心等式中"最大"的部分,然后去掉常数).

如果你有来自1..n 的循环i和来自i..n的j内的另一个循环,它将是O(n ^ 2).