시간 복잡도

Question

죄송합니다

for (int i=0; i<n; i++) { 
    for (int j=0; j<i; j++) { 
     do stuff... 
    } 
} 

은이 코드 n^2 또는 nlogn의 복잡도입니까? 감사합니다.

Answer 1

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

외부 루프의 첫 번째 반복에서, 내부 루프는 외부 루프의 두 번째 반복에서 0 회

을 반복하는 것, 내부 루프 1 회 반복한다.

외부 루프의 세 번째 반복에서 내부 루프는 2 번을 반복합니다.

.........

외부 루프의 n 번째 반복에서, 내부 루프 n - 1 회 반복한다.

반복의 총 수 = 0 + 1 + 2 + 3 + 4 ...... + (n - 1)

우리가 알고있는, 산술 시리즈

1 + 2 + 3 + ..... + (n - 2) + (n - 1) + n = (n * (n + 1))/2 

그래서,

0 + 1 + 2 + 3 + 4 ...... + (n - 1) 
= (n * (n - 1))/2 
~ n^2 

이 일정 시간에 실행됩니다 do stuff 단계를 고려의 합, 전체 시간 복잡도는 O(n^2)입니다.