복잡도와 빅오 표기법

복잡도

---

복잡도는 문제 해결에 사용되는 연산의 횟수를 의미하는 시간복잡도와 프로그램이 종료되기까지 필요한 자원 공간의 양을 의미하는 공간 복잡도로 나뉜다.

 

복잡도는 알고리즘에 데이터가 주어질 때 연산 시간, 혹은 연산에 사용되는 공간의 크기를 객관적으로 비교할 수 있는 기준을 제공하기 때문에, 문제를 해결하는 알고리즘을 평가하는 데에 사용된다.

 

공간 복잡도

---

공간 복잡도란 프로그램을 실행시킨 후 완료하기까지 필요로 하는 공간의 크기를 의미한다.이때 필요한 공간은 고정 공간과 가변 공간으로 나뉜다.

 

• 고정 공간 : 코드가 저장되고, 단순한 변수와 상수가 저장되는 공간. 알고리즘과 무관하다.
• 가변 공간 : 코드가 실행되는 도중에 동적으로 필요한 공간, 알고리즘과 연관된 공간

Big-O 표기법을 사용해 입력된 데이터의 크기와 실제 사용하는 공간 사이의 관계를 표현하면 된다.

시간 복잡도

---

시간 복잡도는 문제를 해결하는 알고리즘의 성능을 표기하는 방법을 의미한다.

Big-O 표기법, O(n)

최악의 경우를 표현하는 표기법이다. 아무리 최악의 상황이라도, 최소한 이 정도의 성능은 보장한다는 의미이기 때문에 Big-O 표기법을 가장 많이 사용한다.

Big-Ω 표기법, Ω(n)

빅 오메가 표기법으로, 최상의 실행시간을 표기한다.

Big-θ 표기법, θ(n)

빅 세타 표기법으로, 알고리즘 평균 실행시간을 표기한다.

 

보통 최악의 경우를 고려하는 Big-O 표기법을 사용한다.

Big-O 표기법

---

Big-O 표기법은 다양한 실행 시간이 존재한다.

O(1), 상수 시간

O(1) 시간 복잡도는 상수 시간을 의미한다.

 

입력된 데이터의 크기와 관계없이 일정한 시간이 소요되는 알고리즘의 시간 복잡도를 표현할 때 사용한다.

아래는 첫 요소를 출력하는 예제를 보면 데이터가 얼마나 많이 들어오는 지에 관계없이 첫 요소만 출력하므로, 일정한 시간이 소요된다.

파이썬

def first_element(arr):
    print(f"배열의 첫 요소는 {arr[0]} 입니다.")

C

void first_element(int* arr) {
	printf("배열의 첫 요소는 %d 입니다.", arr[0]);
}

O(n), 선형 시간

O(n) 시간 복잡도는 선형 시간을 의미한다.

 

 

입력된 데이터의 크기에 비례해서 처리시간이 늘어나는 알고리즘의 시간 복잡도를 표현할 때 사용한다.

 

아래는 반복문 하나를 추가한 예제다. 배열의 모든 요소에 접근하기 때문에, 배열 크기에 정 비례해서 실행 시간이 늘어난다.

파이썬

def first_element(arr):
    for i in range(len(arr)):
        item = arr[i]
        print(f"배열의 {i}번째 요소는 {item} 입니다.")

C

void first_element(int* arr, int size_of_arr) {
	for (int i = 0; i < size_of_arr; i++) 
		printf("배열의 %d번째 요소는 %d 입니다.\n", i, arr[i]);
}

O(2^n) , 지수 시간

O(2^n) 시간 복잡도는 지수 시간을 의미한다.

 

입력된 데이터 크기의 지수 제곱에 비례해서 처리 시간이 늘어나는 알고리즘의 시간 복잡도를 표현할 때 사용한다..

 

대표적으로 재귀 함수로 구현한 피보나치 수열이 존재한다. 피보나치 수열은 입력의 크기가 1 증가할 때마다 실행 시간이 약 두 배로 증가한다.

파이썬

def fibonacci(num):
	if (num <= 1):
		return num;
	
	return fibonacci(num - 2) + fibonacci(num - 1);

C

int fibonacci(num) {
	if (num <= 1) {
		return num;
	}
	return fibonacci(num - 2) + fibonacci(num - 1);
}

 

종합

위에 설명한 O(1), O(n), O(2^n) 이외에도 로그시간, 다항 로그 시간, 2차 시간 등 다양한 시간 복잡도가 존재한다.

 

 

 

Big-O 표기법은 데이터의 입력 개수가 충분히 크다고 가정하기 때문에, 상수항을 무시하고 가장 단순한 형태로 표기한다. 예시로, 최악의 경우 2n의 시간복잡도를 가지는 알고리즘은 O(2n)이 아니라 2를 무시한 O(n)으로 표기한다.

 

정리하면 시간복잡도는 알고리즘이 얼마나 빠른가?를 의미하고, 공간복잡도는 얼마나 많은 자원을 필요로 하는가?를 의미한다.

참조

---

https://codemate.kr/project/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-Level-1/2-1.-%EB%B3%B5%EC%9E%A1%EB%8F%84