[TimeComplexity] 시간 복잡도

💡 알고리즘에 대한 해답을 찾는 것도 중요하지만 시간복잡도를 고려하여 효율적인 코드를 짜는 것도 중요하다.

• ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’라는 말이다.
• 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성해야 한다.

 

❗️Big-O 표기법

Big-O(빅-오) ⇒ 상한 점근 [최악]

Big-Ω(빅-오메가) ⇒ 하한 점근 [최선]

Big-θ(빅-세타) ⇒ 그 둘의 평균 [중간]

Big-O(빅-오) 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 가장 자주 사용된다.

👉 Big-O 표기법의 종류

1. O(1) - 일정한 복잡도
2. O(log n) - 로그 복잡도
3. O(n) - 선형 복잡도
4. O(n2) - 2차 복잡도
5. O(2n) - 기하급수적 복잡도

 

❗️O(1)

**O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

• 이 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.

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

 

❗️O(log n)

O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

• BST(Binary Search Tree)에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
• up & down게임을 예로 들 수 있다.

 

❗️O(n)

**O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

• 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸린다.

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

 

❗️O(n2)

**O(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

• 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸린다.

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

 

❗️O(2n)

**O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

• 매번 실행될 때 마다 2배로 늘어난다.

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

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