알고리즘(Algorithm)에 대한 이해

여러 알고리즘 유형들을 파악하기 앞서 알고리즘이라는 것에 대해 정리해보려고 한다

알고리즘 (Algorithm)

문제를 해결하기 위한 절차나 방법

어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)

반복되는 문제를 풀기 위한 작은 프로시저(procedure;진행절차)

알고리즘 조건

알고리즘은 아래의 조건을 만족해야 한다

• 입력 - 알고리즘은 0 도는 그 이상의 외부에서 제공된 자료가 존재한다
• 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다
• 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다
• 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다
• 효과성 - 알고리즘의 모든 연산들은 사람이 유한한 시간 내 정확하게 수행할 수 있을정도로 충분히 단순해야 한다 

즉 알고리즘은 어떤 입력이 있다면 입력에 따라 명령을 명확하게 실행하고

효과적으로 입력에 따른 결과물을 도출할 수 있다면 알고리즘으로 볼 수 있다는 것이다

※ 명령에 애매함이 있거나 유한한 시간 안에 끝나는 것이 보장되지 않는 경우를 메서드(Method)라고 한다

 

알고리즘 평가

알고리즘의 평가는 효율성 을 중심으로 평가된다

효율성의 핵심은 시간과 메모리라는 두 자원을 소모하는 양에 따라 달라진다

1. 시간복잡도(Time Complexity)

시간 복잡도는 자료의 수 n이 증가할 때 시간이 증가하는 대략적인 패턴을 나타낸 것으로, 대개 Big-O 표기법을 이용한다

간단하게 말하면 입력 자료의 크기 n에 대하여 O(n)의 시간복잡도를 가진 알고리즘은

대략 n에 비례하는 수의 연산을 수행한다고 보면 된다

시간 복잡도가 낮을 수록 더 빠른 연산을 진행할 수 있다

크기 : O(1) < O(logN) < O(N) < O(NlogN) < O($N^{2}$) <  O($2^{n}$) < O(N!) 

big-O표기 안의 1보다 큰 정수는 생략할 수 있다! N이 증가하면 곱해진 상수의 영향을 받지 않기 때문

ex) O(2N) = O(N) / O(4logN) = O(logN) /  O(100) = O(1) ... etc

2. 공간 복잡도(Space complexity)

공간복잡도 역시 Big-O 표기법을 이용한다

시간 복잡도보다는 중요도가 떨어지는데, 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 거의 없다

메모리 문제들은 보통 알고리즘 자체보다는 알고리즘 구현에서 발생하는 문제이기 때문이기도 하다

다만 메모리를 많이 필요로 하는 동적 계획법 등을 사용할 경우에는 공간복잡도까지 함께 신경써야 한다

 

추가)

시간복잡도는 알고리즘의 절대적인 실행시간을 나타내는 것이 아니라

알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는 지를 숫자로 표시한다

여기서 연산은 산술연산(사칙연산)과 대입 연산, 비교 연산, 이동 연산이 있다

알고리즘의 복잡도를 분석할 때는 바로 이들 연산의 실행 횟수를 사용한다

 

참조 : https://namu.wiki/w/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98