알고리즘 기초

알고리즘 = 어떠한 문제를 해결하기 위한 여러 동작들의 집합.

알고리즘의 조건 

입력 : 외부에서 제공되는 자료가 0개 이상 있어야함.

출력 : 적어도 1개 이상의 결과를 만들어 내야 함.

명확성 :  각 명령어는 의미가 모호하지 않고 명확해야 함

유한성 : 한정된 수의 단계 뒤에는 반드시 종료됨. 무한히 동작해서는 안됌. 

유효성 : 모든 명령은 실행 가능한 연산 이어야 함.

알고리즘을 표현 하는 법

자연어 : 사람이 사용하는 일반적인 언어로 표현

순서도(Flow Chart) : 그림으로 도식화 해서 표현

의사코드 (Pseudo Code) : 특정 프로그래밍 언어가 아니라 가상의 언어로 표현.

프로그래밍 언어 : 프로그래밍 언어로 표현.

알고리즘의 분석 기준

1) 시간 복잡도 (Time Complexity)

알고리즘 실행에 걸리는 시간. 실제 걸리는 시간을 측정하는 경우와 실행되는 명령문의 개수를 계산하는 방법이 있는데 시간을 직접 측정하는 경우에는 컴퓨터 성능에 따라 다른 결과를 나타낼 수 있기 때문에 일반적으로 후자의 방법 (연산의 빈도수를 계산하는 방법)을 사용한다.

2) 공간 복잡도 (Space Complexity)

알고리즘 실행에 필요한 저장공간(메모리 or 디스크 공간)이 얼마나 필요한지를 나타낸 것임. 예를 들어 알고리즘 A의 실행 공간이 1MB 필요하고 B의 실행공간이 1KB 필요하다면 공간 복잡도 측면에서 B의 효율성이 1024배 우수한 것.

임베디드 같은 특수한 환경이 아니면 주로 시간복잡도가 훨씬 중요한 평가 기준이 됌. 특별한 언급이 없으면 알고리즘의 성능분석은 시간복잡도를 대상으로 함.

* 시간 복잡도에서 연산 개수 구하기 : 

예를 들어 1부터 100까지의 합을 구한다.

1) 1+2+3+......+100 : 연산 횟수 100번

2) 100*(1+100)/2 : 연산 횟수 3번 (곱셈1, 덧셈1, 나눗셈1)

빅-오(O) 표기법

점근 표기법이라고도 함. 연산의 빈도수를 나타내는 함수 중에서 가장 큰 영향력을 주는 n 에 대한 항만을 표시하는 방법. 일반적으로 계수는 생략 하여 표시함.

예를 들어 O(3n+3)의 복잡도에서 가장 큰 영향을 주는 것은 n차 항임으로 뒤에 있는 3 버리고 앞에 있는 계수를 떼어버리면 이 알고리즘의 시간 복잡도는 n 이 됌.

$f\left(x\right)$와 $g\left(x\right)$인 두 함수를 실함수로 정의하자.
충분히 큰 모든 $x$에 대해서
$\left|f\left(x\right)\right| \leq M\left|g\left(x\right)\right|$ 　 ($x > x_0$)를 만족하는 양수인 실수$M$과 실수$x_0$가 존재하는 경우에만
$f\left(x\right) = O\left(g\left(x\right)\right)$ 이다.


이것은 실수 $a$에 충분히 가까운 $x$에 대해서 $g(x)$가 0이 아닐 때, $\displaystyle \lim_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty$과 동치이다. 

직관적으로 $f\left(x\right)$의 상승률이 $g\left(x\right)$의 상승률보다 클 수 없음을 나타낸다.

수행시간 비교 (출처 : 나무위키)

자료출처 : 위키피디아 및 나무위키