三个嵌套for循环的时间复杂度

Question

有三个嵌套的for循环，如果循环递增1我会发现复杂性但如果循环递增像这样i+=c，我就糊涂了？

    for (int i = 0; i < n; i+=c)
        for (int j = 0; j < i; j++)
             for (int k=0; k < m; k++)
                 result[i,j]= x[j]-y[k]

第三个 for 循环的复杂度是 m，但我认为第一个 for 循环的复杂度是 n/c，第二个 for 循环的复杂度是 n ==> 将范围相乘：n/c * n * m = n^2/c * m ==> 最坏的情况是 O(n^2)。这个对吗？如何使用求和形式求总迭代次数？

Answer 1

时间复杂度取决于您的情况下的两个参数：m 和 n 因为中间循环可以表示为第一个循环的函数。

如果考虑迭代总数，它们的数量级为：

1/2 * m * n * (n-1) = O(mn^2)

左边部分为c=1。但是，给定 c 作为常数，总体时间复杂度不会改变。

如果 c 没有作为常量给出，则最终的时间复杂度将为 O(mn^2)/c

Time Complexity of three nested for loops