[알고리즘] 기초 - 시간 복잡도

 

 

 

시간복잡도 개념

프로그램을 작성할 때 입력의 크기에 따라 프로그램의 계산 횟수가 크게 달라진다.

 

입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이것을 알고리즘의 시간 복잡도라고 한다.

 

 

 

예제

자연수 N이 주어졌을 때 1부터 N까지의 합을 구하는 프로그램 만들기

 

 

[소스 1]

import java.util.Scanner;

public class example{
   public static void main(String[] args){
   int res = 0;
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();

   for(int i=1; i<=N; i++){
       res += i;
   }

   sc.close();
   System.out.println(res);
   }
}

 

[소스 2]

import java.util.Scanner;

public class example{
   public static void main(String[] args){
      int res = 0;
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      res = N * (N+1) / 2
      sc.close();

      System.out.println(res);
   }
}

 

소스 1은 for문을 사용하여 직접 1부터 N까지 더해서 합을 계산했다.

만약 N = 1,000이라면 덧셈이 1000번 일어나고, N = 1,000,000이라면 덧셈이 1,000,000번 일어나야 된다.

즉, 계산하는 횟수가 N에 비례한다.

 

 

 

소스 2는 1에서 N까지의 자연수의 합은 n(n+1)/2 라는 수학 공식을 이용해서 합을 계산했다.

이렇게 하면 N = 1,000이든, 1,000,000이든 무조건 덧셈 한 번과 곱셈 한 번, 나눗셈 한 번으로 계산이 끝난다.

즉, N에 아무 관계없는 상수 시간 안에 계산이 처리된다.

 

 

 

 

모든 알고리즘에는 이와 같이 입력되는 데이터의 크기 또는 개수에 따라 이의 계산 횟수 및 수행 시간이 크게 좌우한다. 입력받는 데이터의 크기에 따른 알고리즘의 수행시간의 변화가 바로 "시간 복잡도"이다.

시간 복잡도가 더 큰 알고리즘들은 더 크거나 많은 데이터를 처리할 때 훨씬 더 오랜 시간이 걸린다.

그런데, 이 계산 횟수의 정확한 측정이 어렵기 때문에 Big O 표기법을 이용해서 표시한다.

 

 

 

 

Big O 표기법

특정 알고리즘의  총 연산 횟수를 간략하게 표현하는 것이다.

 

예를 들어,

입력된 데이터의 객수가 n개일 때 2n + 7번 계산하는 알고리즘과 2n번 계산하는 알고리즘이 있다고 하자. 알고리즘에서 N은 아주 큰 숫자를 의미하는데, n이 커지면 둘 사이의 차이는 사실상 없어진다. 

이를 빅오 표기법으로 나타내면 O(2n + 7) = O(2n) 이다. 대략 O 표기법은 상수만큼의 시간 차이는 무시한다고 보면 된다.

 

 

 

상수는 무시하자

크기 n의 데이터가 들어올 때 n^2번 계산해서 답을 내는 알고리즘과, 1,000n번 계산해서 답을 내는 알고리즘을 비교해 보자.

• n = 10 : 1,000n번 계산하는 알고리즘이 100배 더 느리다.
• n = 1,000 : 두 알고리즘의 속도가 비슷해지고,
• n = 100,000 : n^2번 계산하는 알고리즘이 100배나 더 느려진다.

여기서, n=10 정도의 작은 데이터에서는 100배 더 느려도 0.00001초 정도밖에 차이 나지 않는다.

하지만, 데이터 크기가 커지면 100배 차이는 생각보다 크다. 1000n번 계산하는 프로그램이 0.3초 만에 계산해서 답을 내놓는 사이,  n^2번 계산하는 프로그램은 30초가 지나야 답을 낼 수 있다. 우리가 앞으로 다뤄야 할 데이터는 매우 방대한 양일 것이다. 그러면 두 프로그램의 시간 차이는 기하급수적으로 커지게 된다.

 

 

이때 알 수 있는 것은 계산 횟수에 있는 상수는 중요하지 않다는 것이다. 1,000이라는 상수가 무색해질 정도로 n이 커진다면, n의 증가에 따른 계산 횟수가 훨씬 중요해진다. 그래서 시간 복잡도를 나타낼 때에는 상수는 모두 떼어버린다. 즉, n번 계산, 7n번 계산, 1234n +98382번 계산이든 모두 O(n)으로 나타내는 것이다.

다른 예를 들면, (3^n + 2n^3 + 23417n^2 + 33n log n + 9234)번 계산하는 알고리즘의 시간 복잡도는 O(3^n)으로 간략화된다.

 

 

위의 소스들의 시간복잡도를 구하면, 소스 1은 O(N), 소스 2는 O(1)로 정의할 수 있다.

O(1)은 가장 시간 복잡도가 낮은, 즉 가장 빠른 알고리즘이라고 할 수 있다. 상수의 형태만 가지고 있기 때문에 n의 값이 아무리 커져도 일정한 양의 계산만 하기 때문이다. 

 

출처 : 표 클릭