시간 복잡도란 ?
알고리즘의 효율성을 판단하기 위한 지표로서,
프로그램 수행에 걸리는 절대적 시간이 아닌,
알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.
연산에는 산술, 대입, 비교, 이동이 있다.
시간 복잡도, 즉 성능 측정에 사용되는 표기법은 Big-O, Big-Omega(), Theta(θ) 크게 세 가지로 나뉜다.
시간복잡도 성능지표
Better < < < O(n×log n) < < O(2n) < O(n!) Worse
상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수
log(n) 로그복잡도는 반복문의 O(n) 보다 좋은 성능이며,
nlog(n) 다항복잡도는 이중반복문 O(n2) 보다 좋은 성능입니다.
알고리즘 구현시 반복문을 사용하지 말아야 하는 경우와 사용해도 되는 경우를 잘 구분해야 한다고 합니다. >>케이스 조사 필요
Big-O 표기법별 대표 알고리즘
- : Operation push and pop on Stack
- g n): Binary Tree
- ): for loop
- ×log n): Quick Sort, Merge Sort, Heap Sort
- 2): Double for loop, Insert Sort, Bubble Sort, Selection Sort
- n): Fibonacci Sequence
중요한것은 우리가 자주사용하는 한 차원의 루프를 도는것보다, 로그 복잡도가 더 좋은것이며,
이중 반복문보다 n * log n의 복잡도가 더 낮다는것을 기억해야 합니다.
시간 복잡도 표기 종류
최악 , 최고, 평균의 값을 표기하는 3가지 이름이 있다.
이중에 가장 많이 사용하는건 당연 Big-O 표기법! (최악의 경우를 고려한다)
Big-O - 최악의 경우를 나타냄 (상한 접근)
O(n): 최악의 경우 n번까지 수행되면 프로그램을 끝낼 수 있다.
Big-Omega - 최적의 경우를 나타냄 (하한 접근)
O(n): 최소 번은 수행되어야 프로그램을 끝낼 수 있다.
Theta - 평균 (Big-O 와 Big-Omega값의 평균값)
중요한건 모두 정확한 시간이나 성능 측정의 지표가 아니라, 대략적인 차원에서의 성능적 지표로 사용된다는 것이다.
위와 같이 나눌수도 있고 아래와 같이 4개의 종류로 나누어 표기하는 방법을 사용하기도 한다.
시간 복잡도를 표기하는 다른 종류
Every-case anlaysis
- 입력크기(input size)에만 종속
- 입력값과는 무관하게 결과값은 항상 일정
): Worst-case analysis
- 입력크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최대인 경우 선택
): Average-case analysis
- 입력크기와 입력값 모두에 종속
- 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
- 각 입력에 대해서 확률 할당 가능
): Best-case analysis
- 입력크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우 선택
연관된 글 :
참고 :
'알고리즘 , 문제해결 > 이론' 카테고리의 다른 글
| [알고리즘] 코딩테스트 자주 사용하는 코드 for JAVA (0) | 2023.03.17 |
|---|---|
| [알고리즘] 알고리즘 공부 시작하기 (참고 사이트) (0) | 2023.03.17 |
