[코드트리] 반복문의 시간복잡도(2)

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

반복문 시간복잡도 문제 중 어려웠던 문제입니다.

 

(1)

function solution(n, m)
   set sum = 0
   set visited = [n][m]
   for i = 1 ... i <= n
       for j = 1 ... j <= m
           if visited[i][j] == 0
               for k = j ... k <= m
                   visited[i][k] = 1

for i 문에서는 O(N),

for j 문에서 O(M) 이고,

for k문은 조건문이 만족될 때만 실행되는데... 이게 복잡했습니다.

코드를 분석해보면 if문은 j 반복문이 모두 도는 동안 단 1번만 조건을 만족하기 때문에, for k 문의 시간복잡도는 결국 O(1)이라고 봅니다.

 

-> O(NM)

 

---

(2)

function solution(n, m)
   set sum = 0
   for i = 1 ... i <= n
       for j = 1 ... j <= m
           sum += i * j

   for i = 1 ... i <= n
       sum -= i * i

첫번째 for i 문은 O(N), for j 문은 O(M)

두번쨰 for i 문은 O(N)이므로

총 O(NM + N) ?

 

-> 시간복잡도는 최고 차수만 살리면 되므로, O( N*(M+1) )  =>  O(NM)

 

출처 코드트리