개발/알고리즘

알고리즘과 시간 복잡도

알고리즘의 정의는 어떤 문제를 풀기 위해 정해진 일련의 절차, 방법을 공식화해 표현한 것. 알고리즘은 다음과 같은 특성을 가지고 있다.

 

  • 입력: 0개 이상의 외부에서 제공된 자료가 존재함
  • 출력: 1개 이상의 결과를 가짐
  • 명확성: 각 단계가 명확하고 모호함이 없음
  • 유한성: 단계를 유한한 횟수만큼 반복한 후 문제를 해결하고 종료해야 함
  • 일반성: 정의된 입력들에 일반적으로 적용할 수 있음

 

이처럼 알고리즘은 특정한 문제를 해결할 때 사용되는 방법을 명확하게 나타낸 것이다. 그렇다면 한 문제를 풀 수 있는 알고리즘은 여러 가지가 있을 수 있다. 그렇다면 어떤 알고리즘을 선택해서 문제를 해결해야 할까?

시간 복잡도와 Big-O 표기법

알고리즘의 시간 복잡도는 알고리즘이 답을 내놓기까지 걸리는 시간을 대략적으로 표기하는 방법이다. 대략적으로 나타낸다는 말은 간결하게 나타낸다는 뜻이다. 이게 무슨 뜻일까?

 

우선 Big-O 표기법에 대해 알아보겠다. Big-O 표기법의 정의는 다음과 같다.

 

함수 $f(x),g(x)$에 대해 $f(x)$가 $O(g(x))$라는 것은 어떤 양수 $x_0,c$에 대해 $x_0 \leq x$인 모든 $x$에 대해 $f(x) \leq cg(x)$를 만족한다.

 

몇 가지 예를 들어 보면 다음과 같다.

 

  • $n$: $x_0 = 1, c = 1$이면 $n \leq cn$이므로 $n=O(n)$
  • $3n+1$: $x_0 \geq 4$면 $3n+1 \leq cn$이므로 $3n+1 = O(n)$
  • $n^2+3n$: $x_0 \geq 2$면 $n^2 + 3n \leq cn^2$이므로 $n^2 + 3n = O(n^2)$

 

즉, 최고차항만 남겨두고 계수와 상수를 모두 떼서 나타낼 수 있다. 정확히 하면 시간 복잡도를 나타낼 때 $O(n)$으로 나타낼 수 있는 복잡도를 $O(n^2)$로 나타내지 않으므로 $\Theta$ 표기법이지만, $O$를 이용하여 나타내는 것이 일반적이다.

 

한번 Big-O 표기법을 이용한 시간 복잡도 분석을 해 보자.

 

어떤 양의 정수 $A$와 $B$가 있을 때, $A \leq x \leq B$인 모든 양의 정수 $x$의 평균을 구하려 한다. 표기를 간편하게 하기 위해서, $A$부터 $B$까지의 수의 개수를 $n$이라 하겠다. 가장 간단하게 푸는 방법은 $A$부터 $B$까지의 합을 반복문으로 구하고, 이를 $n$으로 나눈 값을 구하는 것이다. 구현하면 다음과 같다.

#include <iostream>
using namespace std;

int main() {
    int A, B; cin >> A >> B;
    int N = B - A + 1; // A~B의 수의 개수
    int sum = 0;

    for (int i = A; i <= B; i++) sum += i;

    double res = (double)sum / N;
    cout << res;
}

위 코드의 시간 복잡도는 어떻게 될까? 입력으로 어떤 $A$와 $B$가 들어오든 항상 연산을 $n+\alpha$번 하게 된다. $O(n+\alpha) = O(n)$이므로 시간 복잡도는 $O(n)$이라고 할 수 있다.

 

이 문제를 푸는 다른 방법도 존재한다. $A$부터 $B$까지의 합은 $n(A+B) \div 2$로 구할 수 있고, 구현은 다음과 같다.

#include <iostream>
using namespace std;

int main() {
    int A, B; cin >> A >> B;
    int N = B - A + 1;

    int sum = (A + B) * N / 2;
    double res = (double)sum / N;
    cout << res;
}

위 코드에서는 어떠한 경우에도 연산을 일정한 횟수만큼 하게 된다. 따라서 시간 복잡도는 $O(1)$이라고 할 수 있다.

시간 복잡도의 종류

위에서 푼 문제의 첫 번째 해법은 $O(n)$ 시간이 걸린다. 이렇게 입력의 크기에 비례하는 시간을 갖는 알고리즘을 선형 시간(Linear time) 알고리즘이라고 부른다.

 

선형 시간보다 빠르게 동작하는 알고리즘을 선형 이하 시간(Sublinear time) 알고리즘이라고 한다. 대표적인 예에는 이분 탐색($O(\log n$ 시간에 동작함)이 있다. 선형 이하 시간에는 $O(\log n)$, $O(1)$ 등 선형 시간보다 빠르게 동작하는 모든 알고리즘이 포함되어 있다.

 

시간 복잡도가 다항식으로 표현되는 알고리즘을 다항 시간(Polynomial time) 알고리즘이라고 한다. 다항 시간 알고리즘에는 $O(1)$도, $O(n)$도, $O(n^2)$도, $O(n^{10\,000})$도 포함되어 있다. $O(n^2)$와 $O(n^{10\,000})$은 수행 시간에 매우 큰 차이가 있지만 이보다 더 빠르게 증가하는 클래스가 있기 때문에 다항 시간이라는 하나의 분류로 묶는다.

 

지수가 다항식인 식으로 표현되는 알고리즘을 지수 시간(Exponential time) 알고리즘이라고 한다. 지수 시간 알고리즘은 다항 시간과는 비교가 안 될 정도로 매우 빠르게 증가하기 때문에, 입력의 크기가 작을 때에만 사용할 수 있다. 지수 시간보다 더 빠르게 증가하는 알고리즘도 물론 있다.

수행 시간 짐작하기

시간 제한은 당연하게도 시간 복잡도를 분석하여 판단하는 것이 아니라 수행 시간을 기준으로 한다. 그렇다면 이 알고리즘이 시간 내에 돌아갈 지 판단하고 알고리즘을 사용할 것인지 아닌지 결정을 해야 한다.

 

대부분의 경우에, 1초당 연산 횟수가 $10^8$번을 초과하면 시간 제한을 초과할 수 있다라는 주먹구구 방법을 이용한다. 이 방법을 이용하여 최대 입력을 시간 복잡도에 대입해보고 알고리즘이 시간 내에 돌아갈 수 있을지 대략적으로 판단할 수 있다.

 

하지만 예외도 물론 존재한다. Big-O 표기법은 상수와 계수를 모두 삭제하고 나타내기 때문에, 숨겨진 상수나 계수가 매우 크다면 시간 복잡도 상으로는 문제가 없더라도 수행 시간이 훨씬 길어질 수 있다. 또한 연산의 종류에도 수행 시간에 차이가 나는데, 실수 연산/나눗셈 연산/모듈러 연산 등은 꽤 무거운 연산에 속한다. 이러한 경우를 잘 고려하여 시간 제한 안에 돌아갈지 분석해야 한다.

    티스토리툴바