알고리즘의 복잡도

시간 복잡도

 

문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

 

공간 복잡도

 

문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

 

평균 시간 복잡도

 

임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

 

최악 시간 복잡도

 

가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

빅오 notation

점근 표기법의 하나
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
(알고리즘의 복잡도를 표현할 때 흔히 쓰임)

 

o(logn): 입력의 크기의 로그에 비례하는 시간 소요
o(n) : 입력의 크기에 비례하는 시간 소요
계수는 그다지 중요하지 않음

선형시간 알고리즘 - o(n)
예 : n개의 무작위로 나열된 수에서 최댓값을 찾기위해 선형탐색 알고리즘을 적용
최댓값 - 끝까지 다 살펴보기 전까지 알수 없음
average : o(n)
worst-case : o(n)

로그 시간 알고리즘 - o(long)
예: n개의 크기 순으로 정렬된 수에서 특정 값을 찾기위해 이진 탐색 알고리즘을 적용

이차 시간 알고리즘 - o(n^2)
비례관계보다 높은 복잡도

 

삽입정렬 

- best case o(n)
- worst case o(n^2) 역순일때...

 

보다 나은 복잡도를 가지는 정렬 알고리즘
ex) 병합 정렬(merge sort) - o(nlogn)
참고: 입력 패턴에 따라 정렬 속도에 차이가 있지만 정렬 문제에 대해 o(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명됨

-> 반씩 나누고 각각을 정렬시키는 것 o(nlogn)
-> 정렬된 데이터를 두 묶음씩 한데 합친다. o(n)

* 복잡한 문제
유명한 예 : 배낭문제 (Knapsack Problem) --> dynamic programming