study/algorithm
시간복잡도(Big-O)
숲로
2023. 2. 2. 11:31
시간복잡도를 표기하는 방법
- Big-O(빅-오) ⇒ 상한 점근
- Big-Ω(빅-오메가) ⇒ 하한 점근
- Big-θ(빅-세타) ⇒ 그 둘의 평균
- 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법
Big-O
- 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
- “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.
- Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다.
| 표기 예시 | 형태 |
| O(1) | 상수 |
| O(log n) | 로그 |
| O(n) | 선형 |
| O(n log n) | 선형로그 |
| O(n^2) | 다차(polynomial) |
| O(2^n) | 지수 |
| O(n!) | 팩토리얼 |
O(1)의 시간 복잡도를 가진 알고리즘
O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.
O(n)의 시간 복잡도를 가진 알고리즘
O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다
O(n)
O(n^2)
O(