알고리즘이란?
우리는 컴퓨터를 사용합니다. 컴퓨터는 우리의 문제를 해결해 줍니다. 프로그램으로 불리는 것들을 실행할 때, 컴퓨터는 무엇을 하죠? 컴퓨터는 명령어를 수행합니다. 알고리즘이란, 주어진 문제를 풀기 위한 명령어를 단계적으로 나열한 것입니다. 컴퓨터 내에서 실행되는 이상, 알고리즘은 아래의 조건을 만족해야 합니다.
- Input & Output (입출력) – 알고리즘은 0개 이상의 외부 입력과 한 개 이상의 출력이 있어야 합니다.
- Definiteness (명확성) – 각 명령은 모호하지 않고, 명확해야 합니다.
- Finiteness (유한성) – 한정된 수의 단계를 거친 후에는 반드시 종료되야 합니다.
- Effectiveness (유효성) – 모든 명령은 컴퓨터에서 수행 가능해야 합니다.
위의 정리를 종합해 본다면, 아래와 같습니다.
알고리즘은, 주어진 문제에 대한 결과를 도출하기 위해, 컴퓨터가 수행할 수 있는 유한개의 단순명확한 명령들을 순차적으로 구성한 것이다.
알고리즘의 분석
그렇다면 알고리즘은 마땅히 어때야 할까요? 알고리즘은 마땅히 정확하고 효율적으로 우리의 문제를 해결해야 합니다. 따라서 알고리즘을 설계한 다음, 우리는 1. 알고리즘이 얼마나 정확한지, 2. 알고리즘이 얼마나 효율적인지를 분석해야 합니다.
정확성 분석
알고리즘은 0개 이상의 입력이 주어졌을 때, 유한 시간 내에 정확한 결과를 생성해내야 합니다. 이를 증명하기 위해서는 다양한 수학적 기법들을 이용하는데, 해당 블로그에서는 이미 그 정확성이 증명된 알고리즘을 위주로 다루겠습니다.
효율성 분석
효율적인 알고리즘이란 무엇을 의미할까요? 알고리즘이 컴퓨터에서 실행되는 이상, 알고리즘은 적은 메모리를 사용할수록, 적은 시간 안에 문제를 풀어낼수록 효율적이라고 표현할 수 있습니다. 알고리즘이 실행되는데 메모리를 얼마나 잡아먹는지를 공간 복잡도라고 표현하며, 실행시켜 완료할 때까지 걸리는 시간을 시간 복잡도라고 합니다.
- 공간 복잡도
공간 복잡도는 알고리즘을 실행시켜 완료할 때까지 필요한 총 메모리의 양을 의미합니다. 알고리즘을 실행시키기 위해 필요한 공간은, 컴파일 시점에서 결정되는 정적 공간, 실행 시간에 동적으로 결정되는 동적 공간으로 이루어집니다. - 시간 복잡도
시간 복잡도는 알고리즘을 실행시킨 후 완료될 때까지 걸리는 시간을 의미합니다. 하지만 단순 실행 속도는 알고리즘이 어떤 성능을 가진 컴퓨터에서, 어떤 프로그래밍 언어에서, 어떤 환경에서 걸리는 시간 등의 영향을 많이 받게 됩니다. 하여 우리는 그러한 요인들을 배제해야지만 알고리즘의 시간복잡도를 평가할 수 있습니다.- 일반적으로 알고리즘의 수행 시간은 단위 연산의 수행 횟수에 비례하므로, 알고리즘의 수행 시간은 알고리즘이 실행하는 연산의 수행횟수의 합으로 표현할 수 있습니다.
- 알고리즘의 시간 복잡도는 주어지는 입력의 상태에 따라 큰 영향을 받습니다. 알고리즘의 수행 시간을 평가할 때에는 최악의 수행 시간을 그것을 평가하는 척도로 사용합니다. “아무리 최악의 상황이어도, 적어도 이 정도 이상은 안 걸려요” 를 보장해주는 것입니다.
- 알고리즘의 시간 복잡도는 입력 크기 n 에 대한 함수로 표현됩니다.
알고리즘의 점근성능
위에서 알고리즘은 입력받는 데이터의 상태에 따라 영향을 크게 받는다고 언급했습니다. 입력의 크기가 커질수록, 수행 시간은 증가하죠. 예컨대, 일반적으로 무작위로 배열된 1억 개의 데이터를 정렬하는 데에 10개의 데이터를 정렬하는 것보다 시간이 많이 걸립니다.
입력 크기 n 이 무한대로 커짐에 따라 결정되는 성능을 점근성능이라고 합니다. 예컨대 어떤 알고리즘의 수행 시간이 입력 크기 n에 대해 n^3+9n 의 성능을 가진다면, n이 무한대로 커짐에 따라 최고차항 n^3 만이 성능에 영향을 끼치게 됩니다.
그렇다면 이런 점근성능은 어떻게 나타낼까요?
Big-oh표기법
점근적 상한 을 의미하고, 알고리즘의 최악의 수행시간을 의미합니다.Big-omega표기법
점근적 하한 을 의미하고, 최선의 수행시간을 의미합니다.Big-theta표기법
점근적 상한과 하한을 동시에 표시하는 표기법입니다.
알고리즘의 시간 복잡도는 일반적으로 Big-oh 표기법을 사용해 나타내고, 입력 크기 n에 대해 아래와 같은 표기를 주로 사용하게 됩니다.
O(1)– 상수 시간O(logn)– 로그 시간O(n)– 선형 시간O(n logn)– 로그 선형 시간O(n^2)– 제곱 시간O(n^3)– 세제곱 시간O(2^n)– 지수 시간
요약
- 알고리즘은 입출력, 명확성, 유효성, 유한성이라는 네 가지 조건을 만족하는 일련의 컴퓨터 명령을 의미합니다.
- 알고리즘은 공간 복잡도, 시간 복잡도의 두 가지 측면에서 분석될 수 있습니다.
- 입력 데이터 n이 무한대로 증가함에 따라 결정되는 성능을 점근성능이라고 하며, 점근성능을 표현하는 방법에는
Big-oh, Big-omega, Big-theta라는 세 가지 표현 방법이 존재합니다.