我有一个关于计算嵌套在外部 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 之后
这是正确的吗?
谢谢。
最佳答案
这是 O(n)
(您只对等式中“最大”的部分感兴趣,并且去除常数)。
如果你有一个来自 1..n 的循环 i 和来自 i..n 的 j 内的另一个循环,它将是 O(n^2)。
关于java - 用于嵌套一系列 for 循环的大 O,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4294758/