[알고리즘] 시간 복잡도와 Big-O

알고리즘이란

• 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미
• 여러가지 상황에 따른 알고리즘은 모두 다르다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용
• 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는 것

 

시간 복잡도(Time Complexity)

• 알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용
• 최상의 경우 : 오메가 표기법 (Big-Ω Notation) (하한 점근)
• 평균의 경우 : 세타 표기법 (Big-θ Notation) (평균)
• 최악의 경우 : 빅오 표기법 (Big-O Notation) (상한 점근) => 시간 복잡도는 일반적으로 빅오 표기법으로 나타냄.
• 평균인 세타 표기를 하면 가장 정확하고 좋겠지만 평가하기가 까다로움 => 그래서 최악의 경우인 빅오를 사용
• “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능

 

빅오 표기법(Big-O)

• Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법
• 불필요한 연산을 제거하여 알고리즘분석을 쉽게 할 목적으로 사용
• Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있음
  
  • 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
  • 공간복잡도는 알고리즘이 실행될때 사용하는 메모리의 양을 나타낸다. (최근 메모리 기술의 발전으로 중요도가 낮아짐)
• Big-O 표기법의 종류 (아래에서 추가 설명)
  • 1. O(1) - 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리
    2. O(n) - 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐
    3. O(log n) - 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
    4. O(n^2) - 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
    5. O(2n) - 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
• Big-O의 복잡도를 나타내는 표

 

 

 

1. O(1) constant complexity / 상수 시간 (Constant time)

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

let arr = [1, 2, 3, 4, 5]
// arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있음
let index = 1
let result = O_1_algorithm(arr, index)
console.log(result) 
// 2

• O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않음
• 다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미
• 예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있음

 

2. O(n) linear complexity / 선형 시간 (Linear time)

// 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가
function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
    // do something for 1 second
  }
}

// 입력값(n)이 1 증가할때마다 코드의 실행 시간이 2초씩 증가
function another_O_n_algorithm(n) {
  for (let i = 0; i < 2n; i++) {
    // do something for 1 second
  }
}

• O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
• 예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있음
• 2n, 5n 을 모두 O(n)이라고 표기 (*입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미가 점점 퇴색되기 때문)

 

3. O(log n) 로그 시간 (Logarithmic time)

let i = 4

while(Math.floor(i) > 0) {
 i = i / 2
}

console.log(i) // 0.5

• O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
• 이진탐색 BST(Binary Search Tree)에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
• 주로 입력 크기에 따라 처리 시간(연산 횟수)이 증가하는 정렬알고리즘에서 많이 사용 

 

4. O(n2) 2차 시간 (Quadratic time)

// n^2 : 이중반복문
function O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // do something for 1 second
    }
  }
}

// n^3 : 삼중반복문
function another_O_quadratic_algorithm(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(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미
• 반복문이 두번 있는 케이스
• 예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현

 

5. O(2n) 지수 시간 (Exponential time)  - (2n은 2의 n제곱임)

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

• O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
• ex)피보나치 수를 구하는 알고리즘. 한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 2n(2의 n제곱)에 비례해서 연산수가 증가
• 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.

 

---

n의 값이 작을 때는 알고리즘 사이에 큰 차이가 없지만

n의 값이 커지면 커질수록 복잡한 알고리즘은 수행 시간이 급격히 길어짐.

시간 복잡도를 낮출 수 있다면 프로그램에 큰 성능 향상을 기대할 수 있다.