알고리즘의 특성 및 최초의 알고리즘

알고리즘

*문제를 해결하는 단계적 절차 또는 방법

*입력이 주어지고, 알고리즘을 수행한 결과인해(또는 답)를 출력

 

알고리즘의 일반적 특성 

1.정확성

-주어진 입력에 대해 올바른 해를 주어야함 

2.수행성

-각 단계는 컴퓨터에서 수행 가능하여야 함

3.유한성 

-일정한 시간 내에 종료되어야 함

4.효율성

효율적일수록 그 가치가 높아짐

 

최초의 알고리즘 

기원전 300년경 유클리드(Euclid)의 최대공약수 알고리즘

 

최대공약수 

*2개 이상의 자연수의 공약수들 중에서 가장 큰 수 

유클리드 알고리즘 

입력: 정수 a, b (단, a>=b>=0)

출력 a와 b의 최대 공약수 

if b = 0, return a

return Euclid(b, a mod b)

return Euclid(b, a%b)

 

알고리즘 표현 방법

*일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사 코드 (Pseudo Code)로 표현함 

알고리즘의 각 단계는 자연어로 서술할 수도 있으며, 컴퓨터 프로그래밍 언어로 표현할 필요는 없음

ex)

-자연어로 표현된 알고리즘 

-플로 차트(Flow Chart)로 표현된 알고리즘 

-의사 코드로 표현된 알고리즘 

 

자연어 

1. 첫 카드의 숫자를 읽고, 머릿속에 기억해 둠 

2. 다음 카드의 숫자를 읽고, 그 숫자를 머릿속의 숫자와 비교함

3. 비교 후 큰 숫자를 머릿속에 기억해 둠 

4. 다음에 읽을 카드가 남아있으면 Line 2로 감 

5. 머릿속에 기억된 숫자가 최대 숫자임 

 

의사 코드

1. max = A[0]

2.for i = 1 to 0

3.if(A[i] > max) max = A[i]

4.return max

 

플로우 차트

 

 

알고리즘의 효율성 표현 

1.시간복잡도 (Time Complexity) : 알록리즘 수행 시 사용되는 수행시간으로 나타낼 수 있음

-> 일반적으로 알고리즘들을 비교할 때 주로 사용

2. 공간 복잡도 ( Space Complexity) : 알고리즘 수행시 사용되는 메모리 공간의 크기로 나태낼 수 있음

 

시간 복잡도 

* 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현함 

 

복잡도를 표현하기 위한 부석 방법들 

1. 최선 경우 분석(Best Case Analysis)

2.평균 경우 분석(Average Case Analysis)

3. 최악 경우 분석(Worst Case Analysis)

 

 

복잡도의 점근적 표기 

복잡도는 입력 크기에 대한 함수로 표기함 

이 함수는 주로 여러개의 항을 가지는 다항식임 

*단순한 함수로 표현하기 위해 점근적 표기 (Asymptotic Notation)를 사용함 

 

1. O(Big-Oh) -  표기 

*복잡도의 점근적 상한을 나타냄

2. Ω(Big-Omega) - 표기 

*복잡도의 점근적 하한을 의미함 

3. θ(Theta)-표기 

* Ω(Big-Omega) - 표기  와  O(Big-Oh) -  표기  가 같은 경우에 사용함 

 

자주 사용하는 O-표기 

O(1), O(logn), O(n), O(nlogn), O(n²), O(n³), O(2n승)