理解时间复杂度：迭代算法

Question

我是时间复杂度的新手，我似乎无法理解最后得到这个背后的逻辑：

100 (n(n+1) / 2)

对于此函数：

function a() {
    int i,j,k,n;
        for(i=1; i<=n; i++) {
            for(j=1; j<=i; j++) {
                for(k=1; k<=100; k++) {
                    print("hello");
                }
            }
        }
}

以下是我对其算法的理解：

i = 1, 2, 3, 4...n

j = 1, 2, 3, 4...(dependent to i, which can be 'n')

k = 1(100), 2(100), 3(100), 4(100)...n(100)
  = 100 [1, 2, 3, 4.....]

如果我使用上面的算法来模拟最终方程，我会得到这样的结果：

方程式结束：

100 (n(n+1) / 2)

模拟

   i = 1, 2, 3, 4... n
   j = 1, 2, 3, 4... n
   k = 100, 300, 600, 10000

我通常在 youtube 上研究这些并了解 Big O、Omega 和 Theta，但是当涉及到这个时，我无法弄清楚它们是如何以我给出的等式结束的。请提供帮助，如果您有一些最佳做法，请分享。

编辑：至于我自己的假设答案，它认为应该是这个：

100 ((n+n)/2) or 100 (2n / 2)

来源：

https://www.youtube.com/watch?v=FEnwM-iDb2g
At around: 15:21

Answer 1

我认为你的 i 和 j 是正确的，除了不清楚你为什么说 k = 100, 200, 300... 在每个循环中，k 从 1 到 100.

所以让我们先考虑一下内部循环：

        k from 1 to 100:
            // Do something

内循环是O(100) = O(1) 因为它的运行时不依赖于n .现在我们分析外层循环：

i from 1 to n:
    j from 1 to i:
        // Do inner stuff

现在让我们数一数 Do inner stuff 执行了多少次：

i = 1     1 time
i = 2     2 times
i = 3     3 times
 ...        ...
i = n     n times

这是我们的经典triangular sum1 + 2 + 3 + ... n = n(n+1) / 2。因此，外部两个循环的时间复杂度为 O(n(n+1)/2) 减少为 O(n^2).

整个事情的时间复杂度是O(1 * n^2) = O(n^2) 因为嵌套循环使复杂性成倍增加（假设内循环的运行时间独立于外循环中的变量）。请注意，如果我们在各个阶段都没有减少，我们将留下 O(100(n)(n+1)/2)，由于大 O 表示法的属性，它等同于 O(n^2)。

一些提示： 你问了一些最佳实践。以下是我在分析您发布的示例时使用的一些 "rules"。

在时间复杂度分析中，我们可以忽略乘以一个常数。这就是为什么内层循环执行了100次还是O(1)的原因。理解这一点是时间复杂度的基础。我们正在大规模分析运行时，不计算时钟周期数。
对于运行时间相互独立的嵌套循环，只会增加复杂性。将 O(1) 循环嵌套在外部 O(N^2) 循环导致 O(N^2) 代码。
一些减法规则：http://courses.washington.edu/css162/rnash/quarters/current/labs/bigOLab/lab9.htm

如果您可以将代码分解成更小的部分（与我们分析 k 循环与外部循环的方式相同），那么您可以利用嵌套规则来计算组合的复杂性。

关于Omega/Theta的注释：

Theta 是时间复杂度的 "exact bound"，而 Big-O 和 Omega 分别是上限和下限。因为没有随机数据（就像排序算法中那样），我们可以获得时间复杂度的精确界限，并且上限等于下限。因此，在这种情况下，我们使用 O、Omega 或 Theta 没有任何区别。

理解时间复杂度：迭代算法

Understanding time complexity: iterative algorithm

complexity-theory

computer-science

time-complexity