Computer Science/Data Structure

1-4a. 알고리즘의 성능 분석

Study with Me! 2023. 6. 15. 18:06

요즘 컴퓨터는 엄청난 계산 속도와 큰 용량의 메모리를 갖고 있다.

그렇다면 프로그램 작성 시에 계산 시간을 줄이고 메모리를 효과적으로 사용하기 위한 고민은 필요 없을까?

전혀 그렇지 않다.

 

컴퓨터의 성능이 좋아진 만큼 컴퓨터 프로그램이 다루는 자료의 양을 엄청나게 늘어났고 프로그램의 규모도 커졌다.

입력 자료의 개수 프로그램 A : n^2 프로그램 B : 2^n
n = 6 36초 64초
n = 100 10000초 2^100초(4*10^22)년

자료의 크기가 작을 때는 두 프로그램의 성능이 크게 차이나지 않지만,

자료의 크기가 커지면 두 프로그램의 성능 차이는 극명하게 벌어진다.

 

프로그램의 성능에 대해 고민해야 하는 또 다른 이유는 사용자들은 여전히 빠른 프로그램을 선호하기 때문이다.

경쟁 프로그램보다 성능이 떨어지면 소비자들에게 선택되지 못할 것은 당연하다.

 

효율적인 알고리즘이란 실행 시간이 짧으면서 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 알고리즘이다.

일반적으로 실행 시간이 메모리 공간보다 더 중요하게 생각되기 때문에 알고리즘의 실행 시간을 효율적인 알고리즘의 기준으로 삼는 것이 일반적이다.

실행 시간 측정 방법

실행 시간을 축정하는 가장 단순하고 확실한 방법은 알고리즘을 프로그래밍 언어로 작성해 컴퓨터에서 실행시킨 다음, 그 실행 시간을 측정하는 것이다.

동일한 환경에서 서로 다른 알고리즘을 실행했을 때 더 빠른 실행 시간을 갖는 알고리즘이 더 효율적인 알고리즘이 되는 것이다.

 

C/C++에서는 clock() 함수를 이용해 프로그램의 실행 시간을 측정할 수 있다.

이 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환하는데, 반환형은 clock_t 형 이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    clock_t start, finish;
    double duration;
    start = clock();

    /*
        실행 시킬 알고리즘 코드
    */

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;

    printf("%f\n", duration);

    return 0;
}

/*
실행 결과 : 0.000008(초)
*/

하지만 이 방법에는 몇 가지 문제점이 있다.

  • 비교할 두 알고리즘을 "구현"해야 한다.
    알고리즘이 단순한 경우에는 괜찮겠지만 복잡한 알고리즘의 경우엔 부담이 될 수 있다.
  • 비교할 두 알고리즘을 반드시 동일한 조건에서 실행해야 한다.(하드웨어, 소프트웨어 모두)
  • 성능 비교에 사용했던 데이터가 아닌 다른 데이터에 대해서는 다른 결과가 나올 수 있다.

알고리즘의 복잡도 분석 방법

위에서 했던 것과 달리 알고리즘을 직접 구현하지 않고서도 대략적인 효율성을 분석할 수 있다.

이것을 알고리즘 복잡도 분석(complexity analysis)이라고 한다.

이 방법은 구현하지 않고도 모든 입력을 고려하는 방법으로 실행 하드웨어나 소프트웨어 환경과는 관계없다.

 

좋은 알고리즘은 실행 시간이 빠르고, 처리를 위해 필요한 기억 공간이 적은 알고리즘이다.

알고리즘의 실행 시간 분석을 시간 복잡도(time complexity)라고 하고,

알고리즘이 사용하는 기억 공간 분석을 공간 복잡도(space complexity)라고 한다.

알고리즘의 복잡도를 이야기할 때는 보통 시간 복잡도를 말한다.(메모리 공간보다는 실행 시간에 더 관심이 많기 때문)

시간 복잡도 함수

시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌, 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 숫자로 표시한다. 연산에는 산술, 대입, 비교, 이동 연산 등이 모두 포함되는데, 복잡도 분석에는 이들 연산의 실행 횟수를 사용한다.

 

알고리즘을 실행하는데 필요한 연산의 수는 보통 입력의 개수 n에 영향을 받는다.

연산의 수를 n에 대한 함수로 나타낸 것은 시간 복잡도 함수라고 하고 T(n)으로 표현한다.

 

양의 정수 n의 제곱을 구하는 알고리즘 3가지를 비교해보자.

  • 알고리즘 A: 곱셈 연산을 이용해 n과 n을 곱하는 방법
  • 알고리즘 B: 덧셈 연산을 이용해 n을 n번 더하는 방법
  • 알고리즘 C: 덧셈 연산을 이용해 1을 n*n번 더하는 방법
알고리즘 A 알고리즘 B 알고리즘 C
sum ← n * n; for i ← 1 to n do
    sum ← sum + n;		 for i ← 1 to n do
    for j ← 1 to n do
        sum ← sum + 1;

실제로는 덧셈 연산보다 곱셈 연산이 더 빠르게 끝나겠지만 모든 연산에 동일한 시간이 걸린다고 가정하자.

  알고리즘 A 알고리즘 B 알고리즘 C
대입 연산 1 n n*n
덧셈 연산   n n*n
곱셈 연산 1    
전체 연산수 2 2n 2n^2

n이 커질수록 전체 연산수의 차이는 커질 것을 알 수 있고, 가장 효율적인 알고리즘이 무엇인지 판단할 수 있다.

저작자표시 (새창열림)