1. 알고리즘 개요

#알고리즘 이란?

문제 해결 절차를 체계적으로 기술한 것 즉, 입력으로부터 출력을 만드는 과정을 기술한 것이다.

바람직한 알고리즘은 명확해야하며, 효율적이어야 한다. 알고리즘의 평가 기준으로는 1)정확성, 2)수행시간, 3) 사용 메모리 공간, 4)단순성과 명확성, 5)최적성이 있으며, 2번과 3번을 두고 알고리즘의 효율성이라고 한다.

 

#알고리즘의 수행시간 분석

-입력에 따른 수행시간 분석

수행시간은 입력의 크기 n과 관계가 있다. 입력의 크기가 증가하면 알고리즘의 수행시간이 증가한다. 일반적인 생각으로는 수행시간은 크기가 n인 모든 입력에 대한 평균적인 수행시간이라고 생각한다. 하지만 평균적인 수행시간을 분석하는 것은 매우 어렵다. 따라서 크기가 n인 모든 입력 중에서 최악의 경우에 대한 수행시간을 분석한다.

 

-수행시간의 단위

수행시간은 알고리즘의 시작부터 끝까지 실행되는 기본 연산의 개수로 정의된다. 여기서 기본 연산이란 알고리즘의 수행시간에 가장 큰 영향을 미치는 연산이다. 예를 들어, '배열에서 주어진 키의 원소 찾기' 문제가 주어졌을 때 기본연산은 '주어진 키와 배열 원소의 비교'라고 할 수 있다.

 

-최악의 경우 수행 시간(worst case running time) //보통 수행시간을 분석하면 최악의 경우를 분석한다.

수행되는 작업의 양(기본 연산의 수)은 입력의 크기 n에 비례 한다. 입력의 크기가 n일 때, 실행되는 기본연산의 수는 입력 형태에 따라 달라지며 최악의 경우 수행시간은 크기가 n인 모든 가능한 입력에 대하여 실행되는 기본연산 수의 최대값이다. worst의 w를 따서 W(n)으로 표기한다.

 

알고리즘의 수행시간은 T(n)으로 표기한다. T(n) = 실행되는 기본연산의 수 <= W(n)

 

-점근적인 증가율에 의한 함수 분류

입력의 크기가 충분히 클 경우(n이 매우 커질 때) 수행시간을 분석하는 것으로 시간복잡도라는 용어를 사용한다. n이 커질 수록 알고리즘의 효율성이 중요한며 이 경우에 대한 분석 즉, 증가율에 의한 분석을 점근적 분석이라 한다.

함수 증가율 비교

 

-증가율에 의한 함수 표기법

1. Big-O

O(f(n)): 증가율이 f(n)보다 같거나 작은 함수들의 모임으로 최고차 항만 남기고 나머지는 무시한다. 최고차 항에 곱해진 상수도 무시한다. 예를 들어, f(n)=2n+1이면, O(n)으로 표기하며, f(n)=3n*n+n이면, O(n*n)으로 표기한다.

 

 2. Big-Omega: 증가율이 f(n)보다 같거나 큰 함수들의 모임

 3. Big-Theta: 증가율이 f(n)과 같은 함수들의 모임