알고리즘 - 시간 복잡도

다른 개발자들과 함께 알고리즘에 대한 의논을 하게 되면, 자연스럽게 '시간 복잡도' 이야기가 나올 수 밖에 없다.

 

시간 복잡도를 계산할 줄 알아야 원할한 대화가 이루어질 수 있다.

 

알고리즘의 시간 복잡도는 대개 이 중 하나이다.

 

• O(1)

• O(log n)

• O(n)

• O(n log n)

• O(n의 제곱)

• O(n의 세제곱)

• O(n의 네제곱)

• O(2의 n제곱)

• O(n!)

 

이 중에서도 O(1), O(log n), O(n), O(n log n),  O(n의 제곱), O(n의 세제곱) 정도가 많이 사용되고, 나머지는 흔지 않다.

 

 

📍 O(1)

 

O(1)은 인풋의 크키가 소요 시간에 영향이 없다는 뜻이다.

 

function print_first(my_list) {
  console.log(my_list[0])
}

print_first([2, 3])
print_first([2, 3, 4, 5, 7, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])

 

print_first 함수를 처음 호출할 때는 요소가 2개밖에 없는 리스트를 넘겨줬는데, 두 번째 호출할 때는 요소가 16개 있는 리스트를 넘겨줬다. 그런데 사실 두 경우 걸리는 시간은 거의 똑같다. 어차피 맨 앞에 있는 요소를 받아오는 것 뿐이니까 리스트의 길이는 상관이 없다. 길이가 10만씩이나 되는 리스트를 넘겨줘도 똑같을 것이다.

 

반복문이 없으면 대체로 O(1)이다.

 

📍 O(n)

 

Case 1

 

function print_each(my_list) {
  for(let list of my_list) {
    console.log(list)
  }
}

 

반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n)이다.

 

 

Case 2

 

function print_each(my_list) {
  for(let i = 0; i < my_list.length / 2; i++) {
    console.log(my_list[i])
  }
}

 

n번 반복하는 게 아니라 n / 2번 반복한다면 시간 복잡도가 어떻게 될까? O((1/2)n)이지만, 1/2을 버려서 결론적으로 O(n)이라고 할 수 있다.

 

 

Case 3

 

function print_each(my_list) {
  for(let list of my_list) {
    console.log(list)
  }
  
  for(let list of my_list) {
    console.log(list)
  }
  
  for(let list of my_list) {
    console.log(list)
  }
}

 

위 코드의 경우 O(3n)인데, 결국에는 3을 버려서 이것 또한 O(n)이라고 할 수 있다.

 

 

📍 O(n의 제곱)

 

반복문이 연속해서 나오는게 아니라 반복문 안에 반복문이 있는 경우가 있다.

 

function print_each(my_list) {
  for(let i = 0; i < my_list.length; i++) {
    for(let j = 0; j < my_list.length; i++) {
      console.log(my_list[i], my_list[j])
    }
   }
}

 

위 코드처럼 두 반복문 다 인풋의 크기에 비례하는 경우, O(n의 제곱)이라고 할 수 있다.

 

 

📍 O(n의 세제곱)

 

function print_each(my_list) {
  for(let i = 0; i < my_list.length; i++) {
    for(let j = 0; j < my_list.length; j++) {
       for(let k = 0; k < my_list.length; k++) {
      console.log(my_list[i], my_list[j], my_list[k])
       }
     }
   }
}

 

동일한 원리로, 인풋의 크기에 비례하는 반복문이 세 번 중첩되면 O(n의 세제곱)이 된다.

 

 

📍 O(log n)

 

Case 1

 

# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수이다)

function print_powers_of_two(n) {
  let i = 1
 
  while(i < n) {
    console.log(i)
    i = i * 2
  }
  
}

 

이번에는 반복문에서 i가 두 배씩 증가한다.

 

인풋 n이 128이면 반복문이 총 몇 번 실행될까? i 가 1일 때부터 2, 4, 8, 16, 32, 64까지 총 7번 실행된다. 

 

위 함수의 시간 복잡도는 O(log n)이다. 

 

 

Case 2

 

# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)

function print_powers_of_two(n) {
  let i = n
  
  while(i > 1) {
    console.log(i)
    i = i / 2
  }
}

 

i를 n 부터 시작해서 반씩 나눠본다. 이 경우에도 i가 128일 때 부터 64, 32, 16, 8, 4, 2까지 반복문이 7번 실행된다.

 

두 경우 모두 시간 복잡도가 O(log n)이다.

 

 

📍 O(n log n)

 

O(n log n)은 O(n)과 O(log n)이 겹쳐진 것이다.

 

function print_powers_of_two_repeatedly(n) {
  for(let i = 0; i < n; i++) {
   let j = 1
   while(j < i) {
   console.log(i, j)
   j = j *2
   }
  }
}

 

위 코드에서 for문의 반복 횟수는 n에 비례하는데, while문의 반복횟수는 log n에 비례한다. while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 O(n log n)라고 할 수 있다.