알고리즘의 성능분석 방법 - 1장

시간 복잡도와 공간 복잡도

앞서 자료구조를 살펴보았을 때 앞으로 배워야할 자료구조의 종류는 다양했다.

그 이유는 데이터를 표현하는 방법에서 그냥 만능키와 같은 자료구조와 알고리즘은 존재하지 않기 때문이다.

 

그렇기에 우리는 어떤 상황에서 자료구조/알고리즘을 선택해야하는지를 판단할 수 있어야한다.

 

1. 어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가?

2. 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가?

 

이렇듯 알고리즘을 평가하는데에 크게 두 가지 요소가 존재하는데

하나는 '속도'와 관련된 이야기이며 다른 하나는 '공간'에 관한 이야기이다.

속도에 관한 아록리즘의 수행시간 분석결과를 가리켜 '시간 복잡도' 라 하고

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

 

이해하기 쉽게 순차(선형) 탐색 알고리즘의 시간 복잡도를 분석해보자.

#include <cstdio>

int LSearch(int arr[], int len, int target)
{
	// 타켓을 찾으면 target이 존재하는 인덱스를, 못찾는다면 -1을 리턴
	int i;
	for (i = 0; i < len; ++i)
	{
		if (arr[i] == target)
			return i;
	}
	return -1;
}
int main()
{
	
	int arr[] = { 3,5,2,4,9 };
	int idx = LSearch(arr, sizeof(arr) / sizeof(arr[0]), 10);
	if (idx == -1)
		printf("탐색 실패\n");
	else
		printf("인덱스 : %d", idx);

	
	return 0;
}

메인함수에 선언된 배열 arr에 저장된 요소를 LSearch함수를 통해 그 값이 존재하는지 탐색하는 간단한 알고리즘이다.

 

int LSearch(int arr[], int len, int target)
{
	// 타켓을 찾으면 target이 존재하는 인덱스를, 못찾는다면 -1을 리턴
	int i;
	for (i = 0; i < len; ++i)
	{
		if (arr[i] == target)
			return i;
	}
	return -1;
}

우리는 target이 존재하는지가 중요하기 때문에 이 코드를 중심으로 시간복잡도를 평가해본다.

위의 코드는 탐색. 이 배열에 우리가 원하는 값이 존재하는지를 체크해야하기에 값의 비교(==).

즉 배열을 처음부터 끝까지 돌면서 우리가 원하는 값을 빨리찾는다면 ++i나 i < len등의 연산 횟수도 줄어들 것이다.

 

정리하면, 다른 연산들은 == 연산에 의존적이게 된다.

 

만약 내가 찾고싶었던 값이 맨 앞에있으면 금방 찾고 함수를 빠져나오겠지만

최악의 경우는 이 코드는 배열의 맨 마지막까지 탐색을 해야 찾거나, 혹은 찾지 못할경우다.

 

이러할 경우에 시간 복잡도는 최악의 경우 데이터의 수(n)만큼의 시간복잡도가 걸린다고 말한다.

이걸 간단하게 빅오 표기법으로 나타내면 O(n)의 시간복잡도를 가진다고 한다.

 

빅-오 표기법

빅-오 표기법은 기타 다른 모든연산을 포함하지말고 가장 크게 차지하는 비율만 나타내자는게 빅-오 표기법.

 

예로들어 T(n) = n² + 2n + 1 과 같은 시간복잡도가 걸리는 코드가 존재한다면 가장 큰 n²만 보고 그것을

O(n²)라고 표현하자는 것이다.

 

대표적인 빅-오를 살펴보면 밑과 같다.

 

1. O(1)

- 상수형 시간복잡도 혹은 빅오라고 한다. 이는 데이터 수에 관계없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다.

(이 시간복잡도를 가지는 자료구조는 해시-맵)

 

2. O(logn)

- 로그형 시간복잡도 혹은 빅오라고 한다. 예를들어 데이터의 수가 1024개이면 연산 횟수가 단 10번 밖에 안되는 매우 좋은 시간복잡도를 가지는 알고리즘. 

(대표적으로 이진탐색알고리즘,트리등이 존재)

 

3. O(n)

- 선형 시간복잡도 혹은 빅오라고 한다. 이는 데이터의 수와 연산횟수가 비례하는 알고리즘.

(선형 탐색등)

 

4. O(nlogn)

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

(대표적으로 퀵,합병정렬등)

 

5. O(n²)

- 이는 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘이다. 이는 데이터의 양이 많으면 많을수록 부담이 되는 알고리즘. 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산을 진행되는 경우에 발생한다.

 

6. O(n³)

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

 

7. O(2ⁿ)

- 이것을 지수형 시간복잡도 혹은 빅오라고 하는데 이는 한번 연산할때마다 지수적으로 연산횟수가 증가하는 알고리즘. 이는 사용하기가 매우 벅찬 알고리즘이다.

 

빅-오 표기법에서 위에서 아래로 내려올수록 무거운 연산이라고 보면 된다.

 

위는 윤성우님의 열혈 자료구조를 참고하여 복습한것을 정리한 내용입니다.