알고리즘 정렬 - 수행 시간 분석

알고리즘 정렬 - 수행 시간 분석

1. 수행시간 분석이란 무엇인가?

- 문제의 크기(입력의 크기)가 증가함에 따라 처리 시간이 얼마나 증가하는지를 분석하는 것

- 입력의 크기: 입력되는 항목의 개수, 문제의 종류에 따라 입력의 종류 바뀜

=> 배열의 크기

=> 다항식의 차수

=> 행렬의 항목 개수

=> 이진으로 표현된 입력의 비트 수

=> 그래프에서의 정점과 간선 등

2. 알고리즘을 비교하는 객관적 기준

1) 실행 시간

: 컴퓨터에 따라 실행 시간이 달라지기 때문에 좋은 기준이 아님

2) 실행된 구문의 수

: 프로그래밍 언어나 프로그래머의 스타일에 따라 구문의 수가 달라지므로 좋은 기준이 아님

3) 이상적인 해법

: 주어진 알고리즘의 수행 시간을 입력 크기 n에 따른 함수 f(n)으로 표현하고 수행 시간에 따라 이함수들을 비교하면 됨

3. 증가율이란?