Geek asks and answers

The temporary complexity of the triple socket loop?

for(i=0; i<n; i++)
{
    a[i]=0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            a=3;
        }
    }
}

This is a triple nested loop. In my book it is indicated that the operating time: O (N) + O (N ^ 2) = O (N ^ 2)

Shouldn't it be O (N ^ 3)? All three loops depend on each other. He will work for N * N * N times.

+5
source share
3 answers

This is because the loop #1and loop #2use the same count variable iduring the comparison.

At the end of the 2nd cycle using, the ivalue iis n, which also causes it to exit the outer loop. One cycle is completely redundant.

#include <stdio.h>
int main(){
    int x = 0;
    int n = 20;
    int i, j;
    for(i=0; i<n; i++) //this loop runs once
    {
        for(i=0; i<n; i++) //this loop runs n times
        {
            for(j=0; j<n; j++) //this loop also runs n times
            {
                x++;
            }
        }
    }
    printf("%d", x);
}

O(N^2)Everything is done in time.

Example

+6
source

, . : , :

0, . , , i

, O (N), O (N ^ 2)

+1

This is not n ^ 3, since the variable i is reused in the inner loop, making it n ^ 2. Not sure where the book gets O (n) in this.

+1
source

More articles:


All Articles