내부 루프의 반복 횟수가 외부 루프의 현재 반복에 의해 결정되는 중첩 루프의 Big-O는 무엇입니까?

Question

다음 중첩 루프의 Big-O 시간 복잡도는 얼마입니까?

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

일 것이다 오(N^2) 아직?

Answer 1

그렇습니다. 여전히 O (n^2)이지만 일정한 요인이 작지만 O 표기법에는 영향을 미치지 않습니다.

Answer 2

예. Big-O의 정의를 상기하십시오. O (F (N)) 정의상 런타임이라고 말합니다 t (n) ≤ KF (N) 상수의 경우 케이. 이 경우 단계 수는 (N-1)+(N-2)+...+0, 이는 0 내지 n-1의 합으로 재 배열되고; 이것은

t (n) = (n-1) ((N-1) +1)/2.

재정렬하면 볼 수 있습니다 t (n) 항상 ≤ 1/2 (n²)입니다. 따라서 정의에 의해 t (n) = O (n²).

Answer 3

System.out.println을 무시하면 N 제곱입니다.소요 시간이 출력에서 ​​선형이라고 가정하면(물론 그렇지 않을 수도 있음) 결국 O((N^2) * log N)이 될 것 같습니다.

까다롭게 다루려는 것이 아니라 복잡성을 해결할 때 명백한 루프만 고려할 필요가 없다는 점을 지적하기 위해 언급한 것입니다. 호출하는 것의 복잡성도 살펴봐야 합니다.

Answer 4

예, N 제곱입니다. 실제 단계 수는 1에서 n의 합이며, 실수하지 않으면 .5*(n -1)^2입니다. Big O는 가장 높은 지출물과 상수가없는 경우에만 고려하므로 여전히 N 제곱입니다.

Answer 5

n = 10이라면 반복은 다음과 같습니다. 10+9+8+7+6+5+4+3+2+1입니다. (이것은 : 10 개의 반복과 9 개의 반복과 8 개의 반복 등).

이제 N (예에서 10)을 몇 번받을 수 있는지 추가해야합니다.

1 : (10), 2 : (9+1), 3 : (8+2), 4 : (7+3), 5 : (6+4). 5 배나 ... 5 번 반복됩니다.

이제 당신은 당신이 5 개의 tens + 5를 가지고 있다는 것을 알고 있습니다.

10(5) + 5

f (n) (또는 n)의 관점에서, 우리는 이것이 다음을 쉽게 알 수 있습니다.

f (n) = n (n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2 ... 이것은이 중첩 루프의 복잡성입니다.

그러나 큰 O의 점근 적 거동을 고려할 때, 우리는 단일 n 및 분모 인 f (n)의 덜 중요한 값을 제거 할 수 있습니다.

결과 : O (n^2)

Answer 6

내부 루프에서 외부 루프를 통해 시작되는 Afail은 중첩 루프 복잡성을 계산하기에 충분한 방법입니다.