2주차(1) - 알고리즘의 성능분석

알고리즘의 성능분석을 공부하는 이유?

우리가 프로그램을 개발함에 있어서 사용하거나 구상하게 되는 알고리즘은 지정된 범위 내에서 오류없이 잘 동작함을 보장함과 동시에 좋은 성능을 보여줘야 하기 때문이다. 또한 동일한 목표를 구현한 다양한 알고리즘들은 각자 다른 특징과 성능을 가지게 되는데, 이는 개발의 목적과 상황에 따라서 적절하게 선택되어야 하기 때문에 이를 위해서는 알고리즘의 성능평가를 적절하게 수행할 수 있어야 한다.

 

 

알고리즘 성능평가 시 고려되는 두 가지 요소

1. 시간 복잡도 (Time complexity)
2. 공간 복잡도 (Space complexity)

시간 복잡도 (Time complexity)

알고리즘의 수행(실행)시간에 대한 분석, 효율성을 평가하는 척도

공간 복잡도 (Space complexity)

알고리즘의 메모리 사용량에 대한 분석, 효율성을 평가하는 척도

 

 

둘 중에 더 중요한 요소는?

시간복잡도가 더 중요하다.

즉, 알고리즘의 사용하는 메모리 공간보다 실행속도를 더 중요한 요소로 간주한다. 물론 두 알고리즘이 거의 동일한 시간 복잡도를 가지는 경우 둘의 우월을 가리기 위해서 두번째 요소로 공간 복잡도가 활용될 수 있지만 그 이전에는 가장 먼저 시간 복잡도를 고려하게 된다.

 

실제로 컴퓨터가 메모리에 접근하는 횟수가 늘어날수록 처리속도가 느려지게 되기 때문에 (메모리 계층구조) 공간복잡도도 순전히 메모리 공간에 대한 개념만이 아니라 시간에 대한 영향을 미친다고 할 수 있다. 하지만 메모리에 접근함으로서 발생하게되는 알고리즘의 실행시간 저하는 시간복잡도에 비하면 아주 작은 문제이기 때문에 아주 민감한 성능평가가 필요한 것이 아니라면 신경쓰지 않아도 무방하다.

 

즉, 공간 복잡도는 알고리즘의 성능을 평가함에 있어서 보조적인 역할을 수행하는 개념이며, 중요한 것은 시간 복잡도 이다.

 

 

그리고 이 중요한 시간복잡도를 표현하기 위해서 아래의 개념을 사용한다.

Big-O Notation

주어진 데이터의 규모 n에 대하여 어떤 함수의 형태로 실행시간이 결정되는 가를 표현하는 방식

statement-A

for(int i=0 ; i<n ; i++)
    for(int j=0 ; j<n ; j++)
        statement-B

for(int k=0 ; k<n ; k++)
    statement-C

위와 같은 알고리즘이 존재한다고 가정했을 때, 수행되는 명령의 횟수를 계산해보면 아래와 같이 정리할 수 있다.

위의 식에서는 n의 값이 커질수록 n^2의 값이 가장 지배적으로 큰 값을 가지기 때문에 아무리 n의 값이 커진다고 하더라도 그 뒤의 나머지 항들은 시간복잡도의 고려대상에 포함되지 않는다. 이렇게 단정지을 수 있는 이유는 알고리즘에 대한 성능평가를 수행할 때에는 데이터의 수가 매우 많아진 경우에 대해서 다루기 때문이다. 그래서 실행시간을 다항식으로 표현할 수 있다면 최고차항의 지수에만 관심을 가지면 된다. 그래서 위와 같은 함수로 시간복잡도가 표현되는 경우 이를 Big-O Notation으로 아래와 같이 표현한다.

그리고 이를 "Big-O Notation~", "Order of~" 이라고 읽는다.

 

그래서 우리는 다양한 함수식으로 표현되는 시간복잡도를 Big-O Notation을 사용함으로써 다음과 같이 정리할 수 있다.

 

Big-O Notation으로 표현되는 다양한 시간 복잡도의 종류

(실제로는 여기에서 다루는 것 외에도 더 많은 유형의 시간복잡도가 존재한다.)

상수형 Big-O 라고 표현함, 데이터의 수에 상관없이 연산횟수가 고정적인 알고리즘

(실제로 이러한 유형의 알고리즘은 거의 존재하지 않으며, 가장 이상적인 시간복잡도 유형이라고 볼 수 있음.)

 

로그형 Big-O라고 표현함, 데이터의 수가 증가하는 비율에 비해 연산횟수 증가율이 낮은 알고리즘

아주 바람직한 유형, 로그의 밑이 무엇이냐에 따라서 성능이 조금씩 차이가 있지만 그 차이가 알고리즘의 시간복잡도를 비교하는 수준에서는 큰 의미가 없는 수준이기 때문에 무시된다. 예시로 아래와 같은 알고리즘이 있다.

for(int i=1 ; i<n ; i*2) {
    // statement...
}

 

선형 Big-O라고 표현함, 데이터의 수 증가율과 연산횟수 증가율이 비례하는 알고리즘

 

선형 로그형 Big-O라고 표현함, 데이터의 수가 2배로 늘어날 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘

실제로 해당 유형의 시간복잡도를 가지는 알고리즘이 상당 수 존재한다.

 

데이터의 수의 제곱에 해당하는 연산횟수를 필요로 하는 알고리즘

실제로 사용하기에는 다소 무리가 있는 시간 복잡도 유형에 해당하며 이러한 유형은 보통 이중으로 중첩된 반복문 내에서 알고리즘과 관련된 연산이 이루어지는 경우 발생하게 된다. 그렇기 때문에 알고리즘을 기술함에 있어서 중첩된 반복문을 사용하는 것은 그리 바람직한 형태라고 할 수 없다.

 

지수형 Big-O라고 표현함, 데이터의 수에 대하여 지수적인 연산횟수를 필요로 하는 알고리즘

해당 유형의 시간복잡도를 가지는 알고리즘을 실제로 사용한다는 것은 불가능하다. 실제로 구현한 알고리즘의 시간복잡도가 해당 유형을 가지는 경우 이는 알고리즘 개선 및 최적화 과정을 통해서 비교적 현실적인 수준의 시간복잡도를 가지는 알고리즘으로 개선하여 사용한다.

 

그래서 지금까지 살펴본 각 시간복잡도 유형이 동일한 데이터 수를 기준으로 요구되는 연산횟수를 비교하면 아래와 같이 정리할 수 있다.

각 시간복잡도 유형을 그래프로 표현한 것

 

알고리즘 효율성에 대한 분석 필요성

1. 알고리즘의 실용적 유효성을 판단함
2. 데이터의 양이 많아질 때 실행시간을 예측할 수 있도록 함
3. 여러 알고리즘을 비교함으로서 최적의 선택을 할 수 있도록 함
4. 알고리즘을 개선할 수 있는 요소를 발견함

 

참고한 페이지

velog.io/@realryankim/TIL-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95Big-O-notation-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8

TIL | 빅오 표기법(Big O notation) & 자바스크립트