[알고리즘] 알고리즘의 정의와 실행복잡도

컴퓨터 공학에서의 알고리즘

• 어떤 종류의 문제를 해결하기 위한,
• 컴퓨터로 구현이 가능한,
• 명백한 명령어들

좋은 알고리즘의 조건

1. 입력과 출력이 명확히 정의되어 있다.
2. 각 단계가 명확하여 모호하지 않다.
3. 유한 시간 내에 결과를 출력할 수 있다.
4. 같은 문제를 푸는 다양한 방법 중에 가장 효율적이다.
5. 포팅이 불가능한 컴퓨터 코드를 포함하지 않는다.
   (특정 언어에서만 지원하는 기능에 의존하지 않고 다른 언어에 적용할 수 있음)

알고리즘의 효율성

자원(시간과 공간)을 효율적으로 사용하는 알고리즘에 대해 효율이 높다고 표현한다. 시간과 공간은 종종 상반 관계에 있다. 메모리(공간 자원)가 충분한 환경에서는 공간 자원을 소모하여 시간 자원을 아낄 수도 있고 반대로 메모리가 충분하지 않은 환경에서는 시간 자원을 소모하여 공간 자원을 아끼는 선택이 필요할 수도 있다.
자원을 많이 사용할수록 그 알고리즘이 복잡하다고 말하며 알고리즘의 복잡도를 표현하는 방법 중 하나가 빅오(Big-O) 표기법이다.

RAM (random-access machine)

실제 세계에서는 하드웨어마다 공간 자원과 시간 자원의 조건이 다르므로 이론상 알고리즘을 다룰 때에는 모든 알고리즘을 추상적인 공통 기계에서 실행한다고 가정한다.

다양한 하드웨어를 일반적인 형태로 추상화 한 가상의 기계를 랜덤 접근 기계(RAM)라 하며 조건은 아래와 같다.

• 레지스터를 갖춘 단일 CPU 구조이다.
• 정수와 부동소수점 저장이 가능하다.
• 메모리 간접 참조를 지원한다.
• 캐시 메모리와 가상 메모리는 지원하지 않는다.

위와 같은 일반화된 전제 조건에서 효율성을 비교하므로, 실무에서는 실제 실행 환경인 하드웨어에 따라 알고리즘의 이론적 효율과 실제 성능이 서로 다를 수 있다. 따라서 알고리즘의 이론적 성능에 대해서는 정확히 학습하되, 실무에서 하드웨어에 따른 성능을 측정하고 알고리즘을 적용/활용하기 위해서는 컴퓨터 구조 등에 대한 추가 지식이 필요하다.

시간복잡도와 공간복잡도

과거와 비교해 컴퓨터의 발달로 메모리 확보 비용이 줄어들어 공간복잡도의 중요도가 낮아졌다. 알고리즘 학습시에는 주로 시간 복잡도 중심의 분류를 학습한다.

빅오/Big-O

• 점근표기법의 하나로 컴퓨터 공학에서 주로 사용하는 표기법이다.
• 대문자 O를 이용해 표기한다. (O: order of the function)
• 알고리즘 성능을 분류하기 위해 사용한다.
• 입력의 증가에 따른 필요 시간(복잡도)과 공간(복잡도)의 증가량을 측정한다.

O: order of the function
실행시간을 일반화하여 쉽게 분류하려는 목적으로, 함수에서 가장 큰 영향을 미치는 최고차항만 사용하되 계수 또한 무시하고 표현한다.
T(n) = 5n² - n + 3 의 시간 복잡도 O(n²)