[알고리즘] 시간 복잡도

코딩테스트 문제를 풀기 위해 "가장 효율적으로 해결하는 알고리즘" 필요

→ 효율적으로 푸는 것은 제한 시간과 관련이 있으며 문제를 빠르게 푸는 알고리즘 선택

 

알고리즘 수행 시간을 측정하는 방법

1) 절대 시간 측정 : 말 그대로 시간 측정

2) 시간 복잡도 측정 : 알고리즘 시작 순간부터 결괏값이 나올 때까지의 연산 횟수 측정

• 입력 크기 : 입력 크기가 다양하며 이에 따라 결과가 달라지므로 N으로 일반화
• 측정 결과 : 최선(best) / 보통(normal) / 최악(worst)
• 표현 방식 : 점근 표기법으로 사용

 

시간 복잡도 (Time Complexity)

알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수

 

ex) 1차원 배열 검색

• 값을 가장 빨리 찾는 경우 : 검색 시작 위치에 찾을 값이 바로 위치한 경우
• 값을 가장 늦게 찾는 경우 : 찾으려는 값이 없거나 가장 마지막에 위치한 경우

 

점근적 표기법

입력 크기에 따른 연산 횟수의 추이를 활용해 시간 복잡도 표현

• 빅오(Big-O, O) 표기법 : 최악일 때 연산횟수 (수행시간의 상한)   ★ 주로 사용 ★
  • 모든 케이스를 통과해야하므로 주로 최악의 경우인 빅오를 기준으로 계산 
• 빅오메가(Big-Omega, Ω) 표기법 : 최선일 때 연산횟수 (수행시간의 하한)
• 빅세타(Big Theta, Θ) 표기법 : 보통일 때 연산횟수 (수행시간의 상한과 하한)

 

빅오 표기법의 종류

1. O(1) : 상수

입력 데이터 크기에 상관없이 일정한 시간 소요

ex) 스택의 Push / Pop

 

2. O(log N) : 로그

입력 데이터의 크기가 커질수록 처리 시간 감소

ex) 이진트리 / 순기능으로 이루어지는 재귀

 

3. O(N) : 선형

입력 데이터의 크기에 비례해 처리 시간 증가 (N크기만큼 처리 시간 증가)

ex) for문

 

4. O(N log N) : 선형 로그

입력 데이터가 많아질수록 처리 시간이 로그의 배만큼 증가

ex) 퀵 정렬(Quick Sort) / 합병 정렬(Merge Sort) / 힙 정렬(Heap Sort)

 

5. O( N² ) : 다항

입력 데이터를 N만큼 반복하고 그 안에서도 N만큼 반복하여 처리 시간이 급수적으로 증가

ex) 삽입 정렬(Insertion Sort) / 버블 정렬(Bubble Sort) / 선택 정렬(Selection Sort) / 이중 for문

 

6. O( 2ⁿ ) : 지수

입력 데이터가 많아질수록 처리 시간이 기하급수적으로 증가

ex) 피보나치(Fibonacci) 수열

---

※ 참고 자료 ※

https://wikidocs.net/221191

https://aiday.tistory.com/54