중첩 루프의 시간 복잡도는 상위 루프에 따라 다릅니다.

Question

다음 코드에서 T (n)을 찾는 방법. 분석이 필요해.

void abc(int n) { 
    for(int i = 0; i<n; i++){ 
    for(int j = 0; j<i; j++){ 
     System.out.println("Hello World"); 
    } 
    } 
} 

Answer 1

복잡도는 O (N^2)입니다.

자세히. 연산이다 :

T (N) = 1 + 2 + 3 + ... + N = N (N + 1)/2

그래서 O (N^2)

Answer 2

프로그램에서 루프의 복잡성을 계산하려면 프로그램에서 number loop declare를 확인한 다음 중첩으로 호출의 깊이를 확인하면됩니다.

이 코드에서는 하나의 루프와 다른 내부 루프가 복잡해 지므로 O (N^2)로 증가합니다.

그러나 outerloop은 순차적으로 n이고 내부 루프는 i + 1이 될 것이므로 순차적으로 1 + 2 + 3 ... n이되므로 n * (n + 1)/2로 계산됩니다. , 궁극적으로 O (N^2)로 이어질 것입니다.