TIL 06 | 시간 복잡도

1. Time Complexity⏱️ (시간 복잡도)

알고리즘의 수행 시간을 분석할 때 시간 복잡도 사용
수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가

1-1. 시간 복잡도를 고려한다는 것? 🕶️

입력값의 변화에 따라 연산을 실행 할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

• 시간 복잡도를 고민한다는 것 = 효율적인 알고리즘을 고민한다는 것

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

2. Big-O 표기법 ✒️

세 가지 표기법은 각각 최악, 최선, 중간의 경우에 대하여 나타내는 방법이다.

1. Big-O : 상한 점근
2. Big-Ω : 하한 점근
3. Big-θ : 둘의 평균

2-1. Big-O 표기법의 종류 🔑

1. O(1)

일정한 복잡도이다.
입력값이 증가하더라고 시간이 늘어나지 않는다.

=> 입력값의 크기와 관계 없이 즉시 출력값을 얻어낼 수 있다.

2. O(n)

선형 복잡도이다.
입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다.

ex) 입력값이 1일때 1초의 시간이걸린다면, 입력값이 100일땐 100초의 시간이 걸린다.

3. O(log n)

로그 복잡도(logarithmic complexity)이다.
Big-O 표기법 중 O(1) 다음으로 빠른 복잡도를 가진다.

ex) BST의 탐색

4. O(n2)

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

ex) 입력값이 1일 경우 1초가 걸리는 알고리즘에 입력값을 5를 주었더니 25초가 걸리는 것.

5. O(2n)

기하급수적 복잡도(exponential complexity)라고 한다.
Big-O 표기법 중 가장 느린 시간 복잡도이다.

ex) 입력이 늘어날 때 마다 2배로 늘어난다.
피보나치 수열

---

참고
참고 페이지