알고리즘 ] 시간 복잡도(Time complexity)와 시간 복잡도 표기법 / 빅-오(Big-O)

 

  이번 포스팅에서는 시간 복잡도와, 빅-오(Big-O) 표기법을 이용한 시간 복잡도 표현 방법에 대해 알아봅니다.

 

 

본 포스팅은 다음 순으로 작성되었습니다.

1.  시간 복잡도 (Time complexity)
2.  빅-오(Big-O) 표기법

 

1.  시간 복잡도 (Time complexity)

---

    효율적인 알고리즘을 구현하기 위해서는 시간 복잡도를 고려해야 합니다. 이 말은 연산 횟수에 비해 시간이 얼마나 걸리는지를 고려한다는 뜻입니다. 시간 복잡도와 로직의 수행 시간은 비례하는데, 시간 복잡도 수치가 작을수록 효율적인 알고리즘이기 때문입니다.

  

  연산 횟수에 비해 시간이 오래 걸리게 된다면, 실행되는 프로그램이 CPU를 차지하는 시간이 길어지고, CPU가 다른 일을 처리하지 못하기 때문에 전체적인 효율이 떨어질 수밖에 없습니다. 그렇기 때문에 시간 복잡도가 중요한데, 시간 복잡도 표기법은 세 가지가 있습니다.

 

• 빅-오 (Big-O)
• 빅-오메가 (Big-Ω)
• 빅-세타 (Bid-θ)

  이 세 가지 표기법은 각각 최악(상한 점근), 최선(하한 점근), 평균(중간)의 경우에 대해 나타내는 방법입니다. 빅-오 표기법은 최악의 경우를 고려하기 때문에 처리에 필요한 시간의 최대치를 나타냅니다. 최선의 경우나 평균값을 기대하는 시간 복잡도로 알고리즘을 구현하면, 최악의 경우 어디에서 문제가 발생했는지 알아내기 위해 로직의 많을 부분을 파악해야 합니다. 그래서 최악의 경우를 고려하는 빅-오 표기법을 많이 사용합니다.

 

 

2.  빅-오(Big-O) 표기법

---

https://www.bigocheatsheet.com/

 

◼ O(1)

  O(1)은 일정한 복잡도(constant complexity)라 하며, 일정한 복잡도입니다. 입력값이 증가하더라도 시간이 늘어나지 않습니다. 입력값의 크기와 관계없이 즉시 출력값을 얻을 수 있습니다.

function O_1(arr, index) {
	return arr[index]
}

let arr = [1, 2, 3, 4]
let index = 1
let result = O_1(arr, index)

 

---

◼ O(n)

  O(n)은 선형 복잡도(Linear complexity)라 하며, 입력값이 증가함에 따라 시간도 같은 비율로 증가합니다.

function O_n(n) {
  for (let i = 0; i < n; i++) {
    // do something for 1 second
  }
}
function another_O_n(n) {
  for (let i = 0; i < 2n; i++) {
    // do something for 1 second
  }
}

  O_n 함수에서는 입력값 n이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다. 이와 같이 another_O_n 함수는 입력값이 1 증가할 때마다 코드의 실행 시간이 2초씩 증가합니다. 이 경우에 시간 복잡도는 O(2n)이라고 표기하지 않고, O(n)으로 표기합니다. 입력값과 실행 시간이 같은 비율로 증가하고 있기 때문입니다.

 

---

 

◼ O(log n)

  O(log n)은 로그 복잡도(logarithmic complexity)라 하며, O(1) 다음으로 빠른 시간 복잡도를 가집니다.

  예를 들어서 BST(Binary Search Tree)에선 원하는 값을 탐색할 때와 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는데, 이 경우에 O(log n)의 시간 복잡도를 가집니다.

 

---

 

◼ O(n^2)

  O(n2)은 2차 복잡도(quadratic complexity)라 하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가합니다.

function O_quadratic(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // do something for 1 second
    }
  }
}

function another_O_quadratic(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // do something for 1 second
      }
    }
  }
}

  O_quadratic 함수에 입력값으로 5를 주게 되면, 내부 반복분에서 5초의 시간이 걸리고, 그 반복문을 나와 외부 반복문을 수행하게 됩니다. 즉, 내부 반복문이 5번 실행되는 것으로, 5^2초가 걸리게 됩니다.

  another_O_quadratic 함수처럼 반복문이 세 번 중첩된 경우, 5^3초가 걸리게 됩니다. 이 경우들은 모두 O(n^2)의 시간 복잡도를 가집니다.

 

---

 

◼ O(2^n)

  O(2^n)은 기하급수적 복잡도(exponential complexity)라 하며, 빅-오 표기법 중 가장 느린 시간 복잡도를 가집니다. 입력이 늘어날 때마다 시간이 2배씩 늘어납니다. 이 경우 다른 접근 방식을 고민해야 합니다.

function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

  재귀로 구현하는 피보나치수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘입니다.

 

 

---

 

이렇게 시간 복잡도와 빅-오 표기법에 대해서 알아보았습니다.

 

짠!