此嵌套三重for循环的复杂性是什么？ [英] What is the complexity of this nested triple for loop?

问题描述

我在StackOverflow上进行了一些搜索，并了解了直到j循环为止的复杂度，即 O（n 2 ）。但是，由于嵌套了k循环，我感到困惑，因为为什么复杂度变为 O（n 3 ）。有人可以帮我理解吗？

I have searched a bit on StackOverflow and have understood the complexity up to the point of the j-loop, which is O(n2). However with the nested addition of the k-loop, I am confused as why the complexity becomes O(n3). Can someone help me understand this?

据我了解，i循环有n次迭代，j循环有1 + 2 + 3 + ... + n迭代 n *（n + 1）/ 2 ，即 O（n 2 ）

From my understanding, the i-loop have n iterations and the j-loop have 1+2+3+...+n iterations n*(n+1)/2 which is O(n2).

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

编辑：感谢您的所有帮助:) Balthazar，我已经写了一段代码，可以根据它们所在的循环来增加计数器的数量，这是一种循序渐进的粗略方法：

Thanks for all your help guys :) Balthazar, I have written a piece of code to which will increment counters depending on which loop they are in, kinda a crude way of step-by-step:

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

我将此代码从n = 2运行到n = 9，增量为1并具有以下顺序：

I ran this code from n=2 to n=9 with increments of 1 and have got the following sequence:

因此从计数器中可以看出：
i = n-1给出O（n）的复杂度，并且j =（（n-1）* n）/ 2给出复杂度 O（n 2 ）。很难发现K的模式，但是已知K取决于J，因此：

From the counters, it can therefore be seen that: i = n-1 giving the complexity of O(n) and j = ((n-1)*n)/2 giving the complexity O(n2). A pattern for K was hard to spot but it is known that K depends on J, therefore:

k =（（n + 4）/ 3）* j =（n *（ n-1）*（n + 4））/ 6 给出 O（n 3 ）

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 giving a complexity of O(n3)

我希望这对以后的人们有所帮助。

I hope this will help people in the future.

EDIT2：谢谢Dukeling 进行格式化：)在最后一行中也发现了一个错误，现在已纠正

thanks Dukeling for the formatting :) Also found a mistake in the last line, corrected now

推荐答案

如果您习惯于Sigma表示法，这是一种推断算法时间复杂度的正式方法（精确地是简单的嵌套循环）：

If you're accustomed to Sigma Notation, here is a formal way to deduce the time complexity of your algorithm (the plain nested loops, precisely):

NB ：公式简化可能包含错误。如果您检测到任何东西，请告诉我。

NB: the formula simplifications might contain errors. If you detect anything, please let me know.

这篇关于此嵌套三重for循环的复杂性是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！