시간 복잡도

좋은 알고리즘은 문제를 잘 해결하고 효율적인 알고리즘을 말합니다.

문제를 잘 해결하는지는 테스트 케이스를 통한 정확성 결과로 파난하고 효율적인지는 자원(시간, 메모리, 통신 용량) 사용량을 가지고 판단하게 됩니다.

 

 

알고리즘에서 시간 복잡도(Time Complexity)는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다.

일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

입력 크기에 따라 연산 시간이 얼마나 증가하는지 나타내는 함수 입니다.

 

시간 복잡도 유형

 - 빅오메가 \( (\Omega (n)) \): 최선일 때(best case)의 연산 횟수를 나타낸 표기법

 - 빅세타 \( (\Theta (n)) \): 보통일 때(average case)의 연산 횟수를 나타낸 표기법

 - 빅오 \((O(n)) \): 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

보통은 빅오(Big-O notation) 표현법을 사용합니다. 

어떤 연산식에서 최고차항의 차수만 나타내는 방법입니다.

예를 들어, \( 8n^{2}+5n+10 \) 일 때, 최고차항은 \( n^{2} \) 이므로 \( O(n^{2}) \)가 됩니다.

 

여러 빅오 표기법 입니다.

순서는 가장 짧은 시간 순서입니다.

빅오 표기법	이름	사용 예	설명
\( O(1) \)	상수 함수(constant function)	Hash table access	입력의 크기와 관계없이 일정한 시간 소요
\( O(log n) \)	로그 함수(logarithmic function)	Binary search of a sorted table	입력의 크기의 로그에 비례하는 시간 소요. 대체로 매 단계마다 입력의 크기를 절반으로 줄여가는 형태로 동작
\( O(n) \)	선형 함수(Liner function)	Finding an item in an unsorted list	입력의 크기에 비례하여 증가
\( O(n log n) \)	로그-선형 함수(log-liner function)	Quicksort, Merge Sort	대부분의 효율적인 정렬 알고리즘의 시간 복잡도
\( O(n^{2}) \)	이차 함수(quadratic function)	Bubble sort	2중으로 중첩된 반복문을 사용
\( O(c^{n}) \)	지수 함수(exponential function)	Travelling salesman problem solved using dynamic programming	상수 c에 지수 n에 따라 증가
\( O(n!) \)	팩토리얼 함수(factorial function)	Travelling salesman problem solved using brute force	포함된 모든 숫자에 따라 증가