시간 복잡도와 공간 복잡도

시간복잡도와 공간복잡도

시간복잡도와 공간복잡도는 알고리즘이나 자료구조의 성능을 평가하는 척도들을 의미한다.

구분	개념
시간복잡도	입력값의 크기(=개수)와 알고리즘의 연산 수행 시간 간의 상관관계를 분석하여 나타낸 것
공간복잡도	입력값의 크기(=개수)와 알고리즘이 실행시 사용하는 메모리의 양간의 상관관계를 분석하여 나타낸 것.

시간복잡도

시간복잡도란, 입력값의 크기(=개수)와 알고리즘의 연산 수행 시간 간의 상관관계를 분석하여 나타낸 것이다. 이는 알고리즘의 효율성을 평가하는 중요한 척도 중 하나이다. 보통 시간복잡도는 빅오 표기법을 사용한다.

시간복잡도	명칭	설명	예시
O(1)	상수 시간	입력 크기와 상관 없이 항상 일정한 시간이 걸리는 경우, 효율성이 매우 뛰어난 시간복잡도.	배열의 특정 인덱스에 접근 변수 값을 단순히 반환
O(logn)	로그 시간	입력 크기가 증가할수록 실행 시간이 매우 완만하게 증가하는 경우. 비교적 효율적인 시간복잡도.	이진 탐색
O(n)	선형 시간	입력 크기와 실행 시간이 선형적으로 비례해 증가하는 경우. 일반적으로 효율적. 대규모 데이터에서는 더 효율적인 알고리즘을 찾는 게 권장됨.	선형 탐색
O(nlogn)	선형 로그 시간	선형 시간과 로그 시간이 결합된 형태. 입력 데이터를 한 번 순회하면서, 각 단계에서 로그 시간의 작업을 수행하는 경우 발생. 비교 기반 정렬 알고리즘 중에 최선의 시간복잡도. 대규모 데이터 처리에 적합.	병합 정렬, 힙 정렬
O(n^2)	이차 시간	중첩 루프를 사용하는 알고리즘에서 주로 나타나는 시간복잡도 입력 데이터의 각 요소를 다른 모든 요소와 비교하거나 처리해야 하는 경우. 입력 크기가 커질수록 실행 시간이 매우 빠르게 증가. 데이터가 커질수록 비효율적	버블 정렬, 선택 정렬
O(2^n)	지수 시간	입력 크기가 증가할수록 실행 시간이 기하급수적으로 증가하는 시간복잡도 재귀적으로 모든 가능한 경우를 탐색하는 알고리즘에서 나타남 매우 비효율적이며, 현실적으로 큰 데이터 처리가 불가함	피보나치 수열의 비효율적 재귀 풀이
O(n!)	팩토리얼 시간	입력 데이터의 모든 순열을 생성하거나 조합을 시도해야하는 경우 입력 크기가 약간만 커져도 실행 시간이 급격히 증가함 실제로 사용할 수 없는 경우가 많다.	순열 생성 알고리즘

공간 복잡도

공간복잡도란, 입력값의 크기(=개수)와 알고리즘이 실행시 사용하는 메모리의 양간의 상관관계를 분석하여 나타낸 것이다. 이는 알고리짐의 효율성을 평가하는 또 다른 중요한 척도이다. 공간복잡도 또한 빅오 표기법으로 표현된다.

프로그램을 실행할 때에 사용되는 공간은 고정 공간, 가변 공간, 보조 공간 세 가지가 있다. 공간복잡도를 계산할 때에는 기본적으로 이 중 고정 공간과 가변 공간이 사용하는 공간을 대상으로 한다. (공간복잡도의 분석 대상 = 고정 공간 + 가변 공간)

공간복잡도

공간복잡도	명칭	설명	예시
O(1)	상수 공간	입력 크기와 상관없이 일정한 메모리만 사용하는 경우	배열A[n]의 첫 번째 요소를 찾는 함수
O(n)	선형 공간	입력 크기에 선형적으로 비례하여 메모리를 사용하는 경우	입력 데이터 복사
O(n^2)	이차 공간	입력 크기 n에 비례해 n^2의 공간이 필요한 경우	n*n 2차원 배열 생성 함수
		이외 생략

공간의 구분

공간	설명	예시
고정 공간	입력 크기와 관계없이 일정한 크기의 메모리 사용	상수, 고정크기 변수
가변 공간	입력 크기에 따라 달라지는 메모리 공간	배열, 리스트, 스택..
보조 공간	알고리즘 작업 수행동안 임시로 사용하는 추가 공간	임시 배열, 캐시 메모리..

그래프 - 입력 크기에 따른 실행 시간 / 필요 공간