[Algorithm] 알고리즘(Algorithm)이란?

1. 알고리즘(Algorithm)이란?

문제를 해결하는 단계적 절차 또는 방법이다. 

입력 -> 알고리즘 -> 결과  -> 문제 해결

 

특성

• 정확성 : 알고리즘은 주어진 입력에 대해 올바른 해를 주어야 한다. 즉, 모든 입력에 대해 올바른 답을 출력해야 한다. 
• 수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능하여야 한다. 애매모호한 표현을 사용하면 안된다.
• 유한성 : 알고리즘은 유한 시간 내에 종료되어야 한다. 매우 오래 걸리면 알고리즘의 가치를 잃는다.
• 효율성 : 알고리즘은 효율적일수록 그 가치가 높아진다. 항상 시간적, 공간적인 효율성을 갖도록 고안되어야 한다.

 

2. 알고리즘의 표현 방법

 

2-1. 말로 표현된 알고리즘

첫 카드의 숫자를 읽고 기억한다.
다음 카드의 숫자를 읽고, 기억한 숫자와 비교한다.
비교 후 큰 숫자를 기억한다.
다음에 읽을 카드가 있으면 line 2로 간다.
기억한 숫자가 최대 숫자다.

 

2-2. 의사 코드(pseudo code)로 표현된 알고리즘

max = A[0]
for i = 1 to 9
	if (A[i] > max) max = A[i]
return max

 

2-3. 플로차트(flow chart)로 표현된 알고리즘

매우 제한적으로 사용

 

3. 알고리즘의 효율성 표현

알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용 되는 메모리 공간의 크기로 나타낼 수 있다. 이들을 각각 시간복잡도(time complexity), 공간복잡도(space complexity)라고 한다. 일반적으로 알고리즘들을 비교할 때에는 시간복잡도가 주로 사용된다.

 

컴퓨터에서 수행된 시간을 측정할 수 있지만, 실제 측정된 시간은 여러 가지 변수가 있다.(컴퓨터의 성능, 프로그래밍의 언어, 최적화 등등) 따라서, 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.

 

예를 들어, 10장의 숫자 카드에서 최대 숫자를 찾을 때, 비교연산은 총 9번(n-1)이다. 따라서 시간복잡도는 (n-1)이다.

 

효율성 표현

• 공간복잡도 (space complexity) : 극히 제한적인 문제(merge sort) 같은 문제에서나 사용됨
• 시간복잡도 (time complexity)
  • 최악 경우 분석 (worst case analysis) : '어떤 입력이 주어지더라도 얼마 이상을 넘지 않는다'라는 표현
  • 평균 경우 분석 (average case analysis) : 입력이 확률 분포가 균등 분포 (uniform distribution)이라 가정한다. 즉, 입력이 무작위로 주어진다고 가정한다. 
  • 최선 경우 분석 (best case analysis) : 최적(optimal) 알고리즘을 고안하는데 참고 자료로 활용 즉, 이보다 성능이 우수한 알고리즘은 없다.

 

4. 복잡도의 표기

시간(또는 공간) 복잡도는 입력 크기에 대한 함수로 표기, 주로 여러 개의 항을 가지는 다항식이다. 이를 단순한 함수로 표현하기 위해 점근적 표기(asymptotic notation)를 사용한다. 이는 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.

 

예를 들어보자

$ 3n^3 -15n^2+10n-18$ 을 $n^3$으로, $2n^2-8n+3$을 $n^2$으로, $4n+6$을 $n$으로 단순화시킨다. 즉, 다항식의 최고차항만을 계수 없이 취한 것이다. 이 식에 상한, 하한, 동일한 증가율과 같은 개념을 적용하여, 점근적 표기를 사용한다.

 

4.1 점근적 표기

• $O$(Big-Oh)-표기 : 복잡도의 점근적 상한을 나타냄
• $\Omega$(Big-Omega)-표기 : 복잡도의 점근적 하한을 나타냄
• $\theta$(Theta)-표기 : 복잡도의 상한과 하한이 동시에 적용됨을 나타냄

 

$O$(Big-Oh)-표기

O-표기는 복잡도의 점근적 상한 이라는 것을 예제를 통해 살펴보자

$f(n) = 2n^2-8+3$ 이라면, $f(n)$ 의 $O$ -표기는 $O(n^2)$이다.

-> 단순화한 함수 $n^2$에 임의의 상수 c를 곱한 $cn^2$이 $n$이 증가함에 Ekfk $f(n)$의 상한이 된다. 단, $c>0$

    $O$-표기에는 c가 '숨겨져 있다'라고 생각해도 좋다.

 

$\Omega$(Big-Omega)-표기 

$\Omega$(Big-Omega)-표기는 점근적 하한이라는 것을 예제를 통해 살펴보자

$f(n) = 2n^2-8+3$ 이라면, $f(n)$ 의 $\Omega$ -표기는 $O(n^2)$이며 '$n$이 증가함에 따라 $2n^2-8n+3$이 $cn^2$보다 작을 수  없다는 의미이다. 상수 $c$ = 1 로 놓으면 된다. 위와 마찬가지로 최고차항만 계수 없이 취하면 된다.

 

$\theta$(Theta)-표기

$\theta$(Theta)-표기는 복잡도가 위의 2개와 같은 경우에 사용한다. 즉, '$f(n)은 $n$이 증가함에 따라 $n^2$과 동일한 증가율을 가진다

 

4.2 시간복잡도 표기

• $O(1)$              상수 시간 (constant time) 
• $O(logn)$         로그(대수) 시간 (logarithmic time)
• $O(n)$              선형 시간 (linear time)
• $O(nlogn)$       로그 선형 시간 (log-linear time)
• $O(n^2)$          이차 시간 (quadratic time)
• $O(n^3)$          3차 시간 (cubic time)
• $O(2^n)$          지수 시간 (exponential time)
• $O(n!)$