시간복잡도와 공간복잡도

시간 복잡도

시간 복잡도는 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.

모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않기 때문에 연산의 횟수를 센다.

복잡도	소요 시간	예시
O(1)	상수 시간	스택에서 Push, Pop
O(log n)	로그 시간	이진 탐색
O(n)	직선적 시간	for 문
O(n log n)	선형 로그 시간	퀵 정렬(quick sort), 병합 정렬(merge sort), 힙 정렬(heap sort)
O(n^2)	2차 시간	이중 for 문, 삽입 정렬(insertion sort), 거품 정렬(bubble sort), 선택 정렬(selection sort)
O(C^n)	지수 시간	피보나치 수열

공간 복잡도

공간 복잡도는 프로그램 실행과 완료에 얼마나 많은 공간(메모리)이 필요한지를 나타낸다.

공간복잡도는 입력 공간과 추가 공간으로 나뉜다.

공간이 2가지로 나눠지는 이유
입력 공간은 모든 알고리즘이 공통으로 부담하는 비용이고, 추가 공간은 알고리즘 설계에 따라 달라지는 비용이기 때문에 둘을 나눈다.

입력 공간

입력 공간은 프로그램이 실행되기 위해 입력 데이터를 저장하는 데 필요한 메모리 공간이다.

크기 n인 배열을 입력으로 받으면 입력 공간은 O(n)이 된다.

추가 공간

추가 공간은 알고리즘이 입력을 처리하는 과정에서 추가로 사용하는 메모리 공간이다.

반복문 변수 몇 개 → O(1)
재귀 호출 깊이 n → O(n)

일반적으로 공간복잡도는 입력 공간을 제외하고, 추가 공간을 기준으로 분석한다.

빅오 표기법(Big-O notation)

빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정하여 나타내는 것이다.

빅오 표기법에서 n은 입력의 개수를 나타낸다.

아래는 n이 커질수록 알고리즘의 연산량이 어떻게 증가하는가를 나타내는 그래프다.

빅오 표기법 규칙

빅오 표기법 규칙에는 계수법칙, 합의법칙, 곱의법칙, 전이법칙, 다항법칙이 있다.

각 법칙이 어떤 것인지 알아보자

계수법칙

계수법칙은 상수는 무시한다는것이다.

O(3n) → O(n)
O(100) → O(1)

입력 n이 커질수록 상수는 의미가 없어진다.

합의법칙

합의법칙은 여러 단계가 있으면 가장 큰 항만 남긴다는것이다.

O(n + n²) → O(n²)
O(log n + n) → O(n)

느린(큰) 쪽이 전체 성능을 좌우한다.

곱의법칙

곱의법칙은 중첩 반복문은 곱하는것이다.

for n번
└ for m번
→ O(n × m)

전이법칙

전이법칙은 복잡도 비교가 가능하다는것이다.

O(n) ⊂ O(n log n) ⊂ O(n²)

A가 B보다 빠르고, B가 C보다 빠르면 A는 C보다 빠르다.

다항법칙

다항법칙은 최고차항만 남긴다는것이다.

O(n³ + n² + n) → O(n³)