흑미의 블로그

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

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

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

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

=> 배열의 크기

=> 다항식의 차수

=> 행렬의 항목 개수

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

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

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

1) 실행 시간

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

2) 실행된 구문의 수

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

3) 이상적인 해법

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

3. 증가율이란?

데이터형

1. system defined data type(시스템 정의 데이터형)

- int, float, char, double, bool 등

- 각각의 원시 데이터형에 할당된 비트 수는 프로그래밍 언어, 컴파일러, 운영체제에 따라 다름

(출처: 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java)

2. user-defined data type (사용자 정의 데이터형, 원시 데이터형)

- 프로그램 내에서 정의되는 데이터형

- 보통 사용하는 프로그램 작성 언어에 의해 지정된 복수의 데이터형을 조합시킨 것

- 데이터 구조를 만드는 데 사용되는 경우가 많음 

(출처: 한국정보통신기술협회,  http://www.tta.or.kr)

데이터 구조

- 효율적으로 데이터를 사용하기 위해 컴퓨터에 데이터를 저장하고 정리하는 특별한 방법

- 데이터를 정리하고 저장하는데 특화된 체제

- 배열, 파일, 연결 리스트, 스택, 큐, 트리, 그래프 등

1. 선형 데이터 구조

- 항목들이 순차적 차례에 따라 접근되지만 순차적으로 저장되어야 하는 것은 아님

- 연결 리스트, 스택, 큐

2. 비선형 데이터 구조

- 항목들이 비선형의 차례로 저장/접근 됨

- 트리, 그래프

ADT(abstract data type, 추상 데이터형)

- 문제를 푸는 과정을 단순화시키기위해 데이터 구조와 연산을 합쳐 놓은 것

- 두 부분으로 구성

1) 데이터의 선언

2) 연산의 선언

- 주로 사용되는 ADT: 연결 리스트, 스택, 큐, 우선순위 큐, 이진 트리, 딕셔너리, 서로소 집합(Union, Find), 해시 테이블, 그래프 등