代码之家 › 专栏 › 技术社区 › user2005142

if语句嵌套循环的时间复杂度O(N):O(N^4)?

nested-loops big-o time-complexity java

user2005142 · 技术社区 · 7 年前

for(int i = 1 ; i <= n ; i++) {
    for(int j = 1; j <= i*i ; j++) {
        if (j% i == 0){
            for(int k = 0 ; k<j ; k++ )
                sum++;
        }
    }
}

如果i=N,则第二个循环应具有O(N^2)的worsts情况。外环的最坏情况复杂度为O(N)。

然而,if语句保证我们只到达内循环n次,而不是n^2。但不管怎样,我们仍然需要通过外环n*n^2次。if测试是否影响代码段的最坏情况时间复杂度?

2 回复 | 直到 7 年前

Sergey Kalinichenko 7 年前

if ,如下所示:

for(int i = 1 ; i <= n ; i++) {
    for(int j = 1; j <= i ; j++) {
        for(int k = 0 ; k<j*i ; k++ ) {
            sum++;
        }
    }
}

codecrazer 7 年前

    I analyse your question in a more straightfroward way
    we first start by fix i as a costant, 
    for example, assume it to be k,
    so j=1~k^2, when j=k,2k,3k,...,k^2, assume j to be c*k (c=1~k)
    the next loop will be executed c^2 times, 
    so the complexity for a fix i can be expressed as=>
    (1+.....+1)+(1+1+...+2^2)+(1+1+...+3^2)+.....+(1+1+...+k^2)
    = O(k^3)
    so now we set k to be 1~n, so the total complexity will be O(n^4)

推荐文章

jgrewal · java-如何在字符串中查找重复字符并将其连接到新字符串

3 年前