시간 복잡도

자료구조란?

데이터의 표현 및 저장 방법

 

ex) 아래와 같은 배열 선언은 자료구조적 측면의 코드이다.

int arr[5] = {1, 2, 3, 4, 5};

 

알고리즘이란?

데이터를 대상으로 하는 문제의 해결 방법

 

ex) 위에서 선언한 배열의 모든 값의 합을 더하는 반복문의 구성은 알고리즘적 측면의 코드이다.

for(int i = 0; i < 5; ++i)
	sum += arr[i];

 

* 자료구조에 따라서 알고리즘은 달라진다.

* 알고리즘은 자료구조에 의존적이다.

 

 

알고리즘의 성능분석 방법

모든 경우에 있어서 항상 최상의 성능을 보이는 만능 자료구조와 알고리즘은 존재하지 않는다. 

따라서 어떠한 상황에서 최선의 성능을 보일 수 있는지 분석하기 위해 두 가지 요소로 평가 한다.

 

1. (어떠한 상황에서의) 속도

2. (어떠한 상황에서의) 메모리

 

이렇듯 속도에 해당하는 알고리즘 수행시간 분석결과를 가리켜 '시간 복잡도' 라 하고,

메모리 사용량에 대한 분석 결과를 가리켜 '공간 복잡도' 라고 한다.

 

사실 속도가 빠르고 메모리도 적게 써야 최적의 알고리즘이라 할 수 있지만, 일반적으로 알고리즘을 평가할 때는 실행 속도에 초점을 둔다. 더 중요한 요소로 판단되기 때문이다. 특정 알고리즘에 대해서 상대적인 우월성을 입증하는 등의 경우에는 메모리 사용량도 함께 고려가 되지만, 대부분의 경우 속도에 초점을 두어 적합성 여부를 판단 한다.

 

 

시간 복잡도 (Time Complexity)

처리해야 할 데이터양의 변화에 따른 속도의 증가 및 감소 정도를 계산하여 알고리즘의 수행 속도를 평가한다.

 

1. 연산의 횟수를 센다.

2. 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.

(데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산이 되는 식을 구성한다는 뜻)

 

즉, 연산의 횟수가 적어야 빠른 알고리즘이다. 

 

이러한 식을 구성하면 데이터 수의 증가에 따른 연산횟수 변화 정도를 그래프로 나타내어 한 눈에 파악할 수 있다.

따라서 둘 이상의 알고리즘을 비교하기가 용이해진다.

 

시간 복잡도의 기준 - 최악의 경우(Worst case)

시간 복잡도를 분석할 때는 알고리즘마다 핵심이 되는 연산을 찾은 뒤 그 연산을 중심으로 시간 복잡도를 계산한다.

 

예를 들어 아래의 코드와 같은 경우

for(int i = 0; i < len; ++i) {
	if(arr[i] == target)
    	return i;
}

사용된 연산자는 <, ++, == 이렇게 총 3개가 있지만, < 와 ++ 연산은 == 연산에 의존적이다. 비교 연산의 수행 횟수가 늘어나면 나머지 두 연산자의 수행횟수도 늘어나기 때문이다. 따라서 이 경우 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다. 

 

이 때, '최선의 경우(best case)'는 고려하지 않고 '최악의 경우(worst case)'만을 가지고 분석 한다.

 

어떠한 알고리즘이건 최선의 경우(극단적인 예로는 데이터가 1개일 경우)는 대부분 만족할만한 결과를 보이기 때문이다.

따라서 알고리즘을 평가할 때는 최악의 경우를 기준으로 한다.

 

* 평균적인 경우(average case)는 계산하는 것이 쉽지 않기에 일반적인 상황에서는 기준으로 삼지 않는다.

 

빅-오 표기법(Big-Oh Notation)

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 오차 없이 정확히 구하는 것은 대부분의 경우 쉽지 않다.

하지만 시간 복잡도는 정확한 연산 횟수를 계산 하는 용도가 아니라 데이터 수의 증가에 따른 연산 횟수의 변화 정도를 판단하는 것이므로 함수 T(n)에서 가장 영향력이 큰 부분만 따져서 나타내면 된다. 이것을 빅-오 표기법이라 한다.

 

대표적인 빅-오

Big-O Complexity chart

1. O(1)

상수형 빅-오. 데이터 수에 상관없이 연산 횟수가 고정힌 유형의 알고리즘을 뜻한다. 연산 횟수가 1회이건, 3회이건, 100회이건 상관없이 연산 횟수가 고정인 알고리즘은 O(1) 로 표현한다.

 

2. O(log n)

로그형 빅-오. 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘을 의미한다. 

 

3. O(n)

선형 빅-오. 데이터의 수와 연산 횟수가 비례하는 알고리즘을 의미한다.

 

4. O(nlogn)

선형로그형 빅-오. 데이터의 수가 두 배로 늘 때, 연산 횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다. 

 

5. O(n^2)

데이터의 수의 제곱에 해당하는 연산 횟수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적절하다. 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 즉, 중첩된 반복문 사용은 알고리즘 디자인에서 그리 바람직하지 못하다.

 

6. O(n^3)

데이터 수의 세 제곱에 해당하는 연산 횟수를 요구하는 알고리즘을 의미한다. 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이것 또한 역시 바람직하지 못하다.

 

7. O(2^n)

지수형 빅-오. 사용하기에 매우 무리가 있는, 사용한다는 것 자체가 비현실적인 알고리즘이다. 연산 횟수가 지수적으로 증가하기 때문이다. 

 

대표적인 빅-오 표기들의 성능을 비교하자면 아래와 같다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

 

 

※ 위 내용들은 윤성우의 열혈 자료구조 책을 보고 공부한 내용을 정리한 것입니다. 책에 더 자세한 설명이 있습니다!