algorithm - n 和一个精确整数的嵌套 for 循环的复杂性？

Question

我想知道如果 for 循环遍历 n 和 某个指定的整数，如何找到算法的 Big-Oh 复杂性。例如，像这样的函数的复杂度是多少:

for (int i=0; i < n; i++) {
    for (int j=0; j < 100; j++) {
        for (int k=0; k < n; k++) {
            // Some O(1) operation here.
        }
    }
}

现在，我知道外循环和最内循环的复杂度都是 O(n)，但是中间循环的复杂度是多少？ O(100)，这会减少到 O(1) 吗？

Answer 1

是的，只有中间一个是 O(1)。这意味着无论我的输入 n 是什么，它都将运行 100 次。你不能让它循环更多。

但是最外层和最内层它们依赖于n。如果 n 是 100 那么 ouermost 运行 100 次如果它是 1000000 那么是的它运行 1000000 次。

最内层的循环呢？对于最外层的每次迭代，它运行 100*n 次。所以总共会运行 100*n*n 次。

现在想想他们总共做了多少工作？

100n^2+100n+n = An^2+B

O(n^2) 将是时间复杂度。

O(10) 或 O(100) 和 O(100000) 相同吗？

好吧，我会让你免于为任何常量 C 编写更多内容 O(C) 等价于 O(1)。

这里的 C 是 10 或 100 或 100000。