[기타] 시간복잡도

 

시간복잡도

알고리즘의 시간복잡도는 알고리즘을 실행하는데 걸리는 시간을 입력 크기에 따라 표현한 것이다. 입력값이 적을 때는 깊게 고려하지 않지만 실제 개발에서는 방대한 양의 데이터를 다루므로 연산 처리 시간을 최소화하는 방법에 대한 고민이 필수다. 효율적인 방법을 고민한다는 것은 시간복잡도를 고민한다는 말과 같다.

(입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 소요되는지)

시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

 

 

Big-O 표기법

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.

빅-오 표기법은 최악의 경우를 고려하므로 이 정도 시간까지 걸릴 수 있다를 고려해야 그에 맞는 대응이 가능하다.

 

Big-O 표기법의 종류

1. O(1)
2. O(n)
3. O(log n)
4. O(n2)
5. O(2n)

O(1) 일정한 복잡도(constant complexity)

입력값이 증가하더라도 시간이 늘어나지 않는다.

O(n) 선형 복잡도(linear complexity)

입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

O(log n) 로그 복잡도(logarithmic complexity)

Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

O(n2) 2차 복잡도(quadratic complexity)

입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

O(2n) 기하급수적 복잡도(exponential complexity)

Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

 

 

O(2n)의 시간 복잡도를 가진 알고리즘

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

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘이다.
브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다.

 

 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/