[Algorithm] 알고리즘의 분석

- 시간복잡도 : 실행시간은 하드웨어, 운영체제 등과 같은 실행환경에 따라 달리질 수 있기 때문에 실행 시간을 측정하는 대신 연산의 실행 횟수를 측정함. 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 가능.

 

- 점근적 분석 : 데이터의 개수 n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현 하는 기법. 상대적으로 가장 간단하며 알고리즘의 실행환경에 비의존적이기 때문에 광범위하게 사용될 뿐임.

 

- 이진검색 : 정렬된 데이터의 중간값을 비교해 나가는 방식이기 때문에 한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어듬. 즉, 시간복잡도는 O(log2n)임.

=> 순차검색의 시간복잡도는 O(n)이고 이진검색은 O(log2n)이며 둘의 차이는 매우 큼. 

 

① 버블 정렬

② 삽입 정렬

③ 퀵소트 알고리즘 : 최악의 경우 O(n2), 평균 시간복잡도는 O(nlog2n) 

④ 합병 정렬 : 최악의 경우 O(nlog2n)의 시간복잡도를 가짐

⑤ 힙 정렬 : 최악의 경우 O(nlog2n)의 시간복잡도를 가짐