알고리즘 분석
- 정확성 분석
- 유효한 입력, 유한 시간 -> 정확한 결과 생성 증명
- 다양한 수학적 기법을 사용한 이론적 증명이 필요
- 효율성 분석
- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
- 메모리 양 -> 공간 복잡도
- 수행 시간 -> 시간 복잡도
시간 복잡도
- 알고리즘의 수행 시간
- 알고리즘에서 단위 연산의 수행 횟수를 모두 더한 값
- 입력 크기가 증가하면 수행 시간도 증가
- 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현
- 입력 데이터의 상태에 종속적
- 평균 수행 시간, 최선 수행 시간, 최악 수행 시간
- 컴퓨터에서 실행시켜 완료될 까지 걸리는 실제 시간을 측정하는것은 컴퓨터의 종류와 속도, 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 종속적이므로 일반성 결여
점근성능
- 입력 크기 n이 충분히 커짐에 따라 결정되는 성능
- 다항식의 수행 시간에서 가장 큰 영향을 미치는 것은 계수없이 ‘최고차항’만을 이용해서 표현
- 수행 시간의 어림값, 수행 시간의 증가 추세 - 알고리즘의 우열
| 효율적 |
|
|
|
|
|
비효율적 |
| 상수 시간 |
로그 시간 |
선형 시간 |
로그 선형 시간 |
제곱 시간 |
세제곱 시간 |
지수 시간 |
| O(1) |
O(logn) |
O(n) |
O(nlogn) |
O(n^2^) |
O(n^3^) |
O(2^n^) |
정렬 알고리즘
기본 개념
- 내부 정렬
- 모든 데이터를 주기억장치에 적재한 후 정렬하는 방식
- 외부 정렬
- 모든 데이터를 주기억장치에 저장할 수 없는 경우, 일부 데이터만 주기억장치에 있고 나머지는 외부기억장치에 저장한 채 정렬하는 방식
- 비교 기반
- 선택 정렬 / O(n^2^)
- 버블 정렬 / O(n^2^)
- 삽입 정렬 / O(n^2^)
- 퀵 정렬 / O(nlogn)
- 합병 정렬 / O(nlogn)
- 분포 기반
- 계수 정렬 / O(n)
- 기수 정렬 / O(n)
선택정렬
- 주어진 데이터 중에서 가장 작은 값부터 차례대로 선택해서 나열하는 방식
- O(n^2^)
버블 정렬
- 왼쪽에서부터 모든 인접한 두 데이터를 차례로 비교하여 왼쪽의 값이 더 큰 경우에는 오른쪽 값과 자리를 바꾸는 과정을 통해 정렬
- 원하는 순서로 이미 정렬되어 있는 경우
- 역순으 정렬되어 있는 경우
- 선택 정렬에 비해 데이터 교환이 더 많이 발생
삽입 정렬
- 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식
- 입력 배열을 정렬 부분과 미정렬 부분으로 구분
- 미정렬 부분의 가장 왼쪽에 있는 데이터(첫번째 데이터)를 꺼낸 후, 정렬된 부분에서 제자리를 찾아 삽입하는 과정을 반복
- 역순으 정렬되어 있는 경우
- 선택 정렬에 비해 데이터 교환이 더 많이 발생
