[알고리즘] 시간복잡도

 

 

 

 

 

 

 

 

 

시간복잡도(Time Complexity)

---

 

 

 

 

 

알고리즘 평가

 

알고리즘의 평가는 효율성을 분석하는 것입니다.  알고리즘 평가법에는 시간복잡도와 공간복잡도가 있습니다. 

 

• 시간복잡도 : 알고리즘의 수행시간의 효율성 분석
• 공간복잡도 : 알고리즘 수행에 필요한 메모리 양을 평가 

 

 

시간복잡도

 

시간복잡도(Time Complexity)란 알고리즘이 문제를 해결하는데 필요한 시간을 나타내는 개념입니다. 

 

다시 말해 시간복잡도란 입력된 데이터의 크기에 따라 알고리즘이 얼마나 많은 시간이 걸리는지를 나타내는 것입니다. 

 

일반적으로 1억 번의 연산을 1초로 간주하여 측정합니다. 

 

 

 

 

시간복잡도 표기법

 

• 빅 오 표기법 O(Big O) : 최악의 연산 횟수를 나타낸 표기법
• 빅 세타 표기법 θ(Big Theta) : 보통의 연산 횟수를 나타낸 표기법
• 빅 오메가 표기법 Ω(Big Omege) : 최선의 연산 횟수를 나타낸 표기법  

 

 

 

빅 오 표기법 (Big O)

 

• 정확한 실행 횟수 보다 n이 커짐에 따라 어떤 비율로 시간이 증가하는지가 중요
• 데이터크기 n과 상관없이 상수 번 실행되는 명령문은 무시해도 됨
• n에 의존하는 항이 여러 개인 경우, 차수가 제일 높은 항이 전체 시간을 지배 

 

 

 

상수시간 O(1) 

ex) 홀/짝 판별, 해시 테이블 평균적인 검색 

 

로그시간 O(log n) 

ex) 이진 탐색 

 

선형시간 O(n) 

ex) 배열에서 최대값 찾기, 해시맵을 사용해 배열 중복 요소 찾기 

 

선형로그시간 O(n log n)

ex) 병합 정렬

 

제곱 시간 O(n^2)

ex) 배열의 중복 요소 찾기, 버블 정렬 

 

지수 시간 O(a^n)

ex) 모든 부분 집합 찾기 

 

팩토리얼 시간 O(n!)

ex) 주어진 집합/문자열의 모든 순열 찾기 

 

 

 

연산 횟수 계산법

 

연산 횟수 계산을 통해 어떤 알고리즘을 사용하는 것이 적합한지 대략적으로 파악할 수 있습니다. 

 

연산 횟수 공식 : 알고리즘 시간 복잡도 x 데이터 크기(n) 

 

 

 

정렬 알고리즘 Big O

• 선택정렬 O(n^2)
• 버블정렬 O(n^2)
• 삽입정렬 O(n^2)

 

탐색 알고리즘 Big O

• 선형탐색 O(n)
• 이진탐색 O(log n)