java - 用于嵌套一系列 for 循环的大 O

Question

我有一个关于计算嵌套在外部 for 循环中的一系列循环的 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(N-2)

4N - 4

O(4N - 4)

O(4N) - 移除常量 -4 之后

这是正确的吗？

谢谢。

Answer 1

这是 O(n)

(您只对等式中“最大”的部分感兴趣，并且去除常数)。

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