알고리즘 개요

알고리즘

알고리즘이란 어떤 문제를 해결하기 위한 동작들의 모임이다.

알고리즘은 유한한 시간 이내에 종료되어야 하며,

명확한 단계로 표현될 수 있어야 한다.

또한 보편적으로 다음과 같은 성질을 지니고 있어야한다.

• 입출력 : 알고리즘은 1개 이상의 입력과 출력을 가지고 있어야 한다.
• 명확성 : 알고리즘의 수행과정은 모호하지 않고 명확하게 표현되어야 한다.
• 유한성 : 알고리즘은 유한한 시간과 공간 내에서 해결되어야 한다.
• 효율성 : 알고리즘의 각 수행과정이 성능적으로 분석 가능해야 한다.

알고리즘의 성능분석 기준

알고리즘의 성능을 평가하기 위해서 주로 사용되는 기준은 다음과 같다.

• 정확성 : 올바른 입력이 입력되었을 때, 올바른 결과가 나와야 한다.
• 소요시간 : 알고리즘이 종료될때까지 걸린 시간.
• 소요공간 : 알고리즘이 종료될때까지 사용된 메모리의 양.

하지만 소요시간과 소요공간은 입력에 따라 매번 바뀔 수 있다. 

가장 단순하게, 정렬 알고리즘에서 다음과 같은 경우를 생각해보자.

• 이미 정렬된 배열을 입력으로 넣은 경우.
• 그렇지 않은 경우.

이미 정렬된 배열의 경우에는 swap 연산이 단 한번도 발생하지 않겠지만,

그렇지 않은 경우에는 매번 swap 연산이 발생할 것이다.

이렇듯 입력에 따라 알고리즘의 성능이 바뀔 수 있으므로,

성능을 분석할 수 있는 명확한 기준이 필요하기 때문에,

해당 알고리즘이 낼 수 있는 최악의 성능이 보편적인 기준으로 많이 쓰인다.