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

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

 

function example(n)
  while 0 > n or n > 100
    if n < 0
      n++
    else
      n--
  return n

 

위 코드의 경우 n에 값에 따라 연산의 횟수가 달라질 수 밖에 없습니다.

사실, 시간복잡도는 일반적으로 최악을 기준으로 계산합니다. 우리가 시간복잡도를 계산하는 이유가 프로그램의 성능을 체크하기 위함이었죠? 당연히 입력값이 아주 크거나 시간이 오래 걸리는 데이터도 들어올 가능성이 존재하므로 최악의 경우를 고려하면 어떠한 상황에서도 프로그램의 성능이 뛰어난지 확인할 수 있을 것입니다.

이 점을 상기한 채로, 반복문의 시간복잡도에 대해 알아봅시다.

 

---

for

set x = 0
for i = 0 ... i < 10
  x += 1
  print(x)

 

for문 한번의 시간복잡도는 O(1)이므로, 10번 반복을 해도 결국 시간복잡도는 O(1∗10)=O(1) 입니다.

 

그러나 불분명한 값이 들어오게 되면 상황은 달라집니다.

function example(n)
  set x = 0
  for i  = 0 ... i < n
    x += 1
    print(x) 

 

조금 당황스러울 수도 있지만 for문 내부의 코드의 시간복잡도는 O(1)이니, N번 반복을 수행하게 된다면 O(N)이 됩니다.

 

set x = 0
for i = 0 ... i < n / 2
  x += 1
  print(x)

 

위의 코드는 2n​번 수행이 되겠지만, O 표기법은 상수를 무시하기 때문에 마찬가지로 O(N) 입니다.

---

while

while 문의 경우, 반복문을 탈출할 수 있는 조건이 불분명 하므로 for에 비해 생각해야 할 것이 많습니다.

function example(n)
  while 0 > n or n > 100
    if n < 0
      n++
    else
      n--
  return n

 

n이 만약에 엄청나게 큰 값이라면 이론적으로 N - 100회의 순회가 필요할 것 입니다.

따라서 시간복잡도는 자연스럽게 O(1∗(N−100))=O(N) 이 될 것 입니다.

---

 

set x = 0
for i = 0 ... i < n
  for j = 5 ... j < n
      x += 1
      print(x)

for i = 0 ... i < n
    x += 1

print(x)

 

위 코드의 포문은 O(N^2), 아래 포문은 O(N) 이지만 N^2이 항상 N보다 크거나 같으므로

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

 

반복문이 중첩되면 바깥 반복문과 내부 반복문을 모두 고려해야 하기 때문에 시간복잡도를 판단하기 조금 어렵습니다.

function solution1(n)
    for i = 1 ... i <= n
        for j = 1 ... j <= 5
            for k = 1 ... k <= n
                    print("Hello")

-> N*5*N = O(N^2)

 

다음 코드는 정렬 알고리즘 코드 중 하나인 선택 정렬의 코드로, 다른 정렬 알고리즘에 비해 간단하다는 장점이 있습니다.

function Selection_sort(arr)
  set len = arr.size
  for i = 0 ... i < len-1
    set min = i
    for j = i+1 ... j < len
      if arr[j] < arr[min]
        min = j
    set tmp = arr[i]
    arr[i] = arr[min]
    arr[min] = tmp
  
  return arr

-> O(N^2)

 

function solution1(n)
 for i = 0 ... i < n * n
   for k = 0 ... k <= i
     print("Hi")
   for j = n ... j >= 0
     print("Bye")

->  (N^2)*(N^2) + (N^2)*N  =>  O(N^4) (둘중 더 큰 값)

function solution2(n)
  for i = 0 ... i < n
    set j = 1
    while j < i
      j *= 2

위 코드는 for문 안에 while문이 있는데,

i가 2배 늘어날때마다 while문은 반복 횟수가 1씩 늘어나므로 총 log i 번 반복이 필요합니다.

따라서 시간복잡도는 for문은 N, while문은 log N 이라고 볼 수 있습니다.

 

-> O(N logN)

 

출처 코드트리