알고리즘이란?
알고리즘(algorithm)은 주어진 문제를 해결하기 위한 유한한 명령어의 집합입니다. 이 명령어들을 순서대로 따라가면 특정 작업을 수행하거나 문제를 해결할 수 있습니다. 알고리즘은 특정 프로그래밍 언어에 종속되지 않기 때문에, 어떤 언어나 기호를 사용해서도 표현할 수 있다는 것이 큰 특징입니다.
알고리즘이 갖추어야 할 5가지 조건
하나의 알고리즘이 제대로 된 알고리즘이라고 인정받으려면 다음 다섯 가지 조건을 모두 만족해야 합니다.
- 입력(Input): 외부에서 0개 이상의 입력이 알고리즘에 제공됩니다.
- 출력(Output): 최소 한 개 이상의 결과물을 반드시 산출해야 합니다.
- 명확성(Definiteness): 각 명령어는 누가 해석하더라도 동일하게 이해될 수 있도록 명확하고 모호함이 없어야 합니다.
- 유한성(Finiteness): 어떤 경우에도 유한한 단계 안에서 반드시 종료되어야 합니다.
- 유효성(Effectiveness): 각 명령어는 충분히 기본적인 수준이어야 하며, 그 목적이 분명하게 드러나야 합니다.
알고리즘 분석이란?
알고리즘 분석은 계산 복잡도(computational complexity) 이론의 핵심적인 부분입니다. 복잡도 이론은 알고리즘이 주어진 계산 작업을 수행하는 데 필요한 자원에 대한 이론적 추정치를 제공합니다.
알고리즘 분석은 알고리즘의 문제 해결 능력을 실행 시간과 필요한 저장 공간(메모리)의 관점에서 평가하는 과정입니다. 그중에서도 분석의 가장 큰 관심사는 알고리즘이 요구하는 실행 시간, 즉 성능입니다.
알고리즘의 복잡도(Complexity)
알고리즘의 복잡도란 입력 크기(n)에 따라 알고리즘이 필요로 하는 시간과 공간의 양을 측정한 것입니다. 복잡도는 크게 두 가지 유형으로 나눌 수 있습니다.
- 시간 복잡도(Time Complexity)
- 공간 복잡도(Space Complexity)
일반적으로 이러한 복잡도는 빅오(Big-O) 표기법과 같은 점근적 표기법으로 나타내며, 이를 통해 입력 크기가 커질 때 알고리즘의 성능이 어떻게 변화하는지 예측할 수 있습니다.
시간 복잡도(Time Complexity)
시간 복잡도는 알고리즘을 실행하는 데 소요되는 총 시간에 대한 공식을 도출하는 과정으로 정의됩니다. 이 계산은 특정 구현 방식이나 프로그래밍 언어와 완전히 독립적이며, 오직 알고리즘 자체의 논리적 구조에만 기반합니다.
공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘이 성공적으로 실행되기 위해 필요한 메모리 공간의 크기를 예측하는 공식을 정의하는 과정입니다. 여기서 말하는 메모리 공간은 일반적으로 주기억장치(main memory)를 기준으로 합니다.