Complexity

4 Feb 2025

시간 복잡도와 공간 복잡도

알고리즘의 성능, 효율성을 나타내는 척도
시간 복잡도 , 공간 복잡도 로 나눌 수 있다.
각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.
복잡도를 나타내는 방법으로는 점근 표기법으로 빅오, 오메가, 세타 등이 있는데 주로 빅오 표기법을 사용한다.

즉, 어떤 알고리즘이 얼마나 효율적인지를 표현하는 방법이라고 생각하면 된다. 알고리즘을 평가할 때 수행 시간과 메모리 사용량을 기준으로 둔다.

시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다. 알고리즘의 성능 평가 case는 3가지가 존재한다

보통 알고리즘에서 시간 복잡도를 표현한다면 최악의 경우 를 기준으로 알고리즘 성능을 파악한다.

공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리) 가 필요한지를 나타낸다. 알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.

알고리즘과 무관한 공간, 고정 공간
- 코드가 저장되는 순간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간
알고리즘과 밀접한 공간, 가변 공간
- 문제를 해결하기 위해 알고리즘이 필요로 하는 공간. 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택 등

시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다. 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 파악할 때는 시간 복잡도를 위주로 사용한다.

빅오 표기법은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다. 빅오 표기법이 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문인데 즉, 최악의 경우 를 고려하는데 가장 좋은 표기법이다.

ps. 무슨 수학적 정의가 있는데 딱히 심각하게 볼 필요는 없는거 같다… 대학 알고리즘 수업땐 코드보면서 주구장창 빅오표기법 계산 과제만 수두룩…

상수항 무시
- 빅오 표기법에서 n은 무수히 크다고 생각하기 때문에 (O(2n)) 과 같이 계산이 나왔다면 상수항은 제거하고 (O(n)) 으로 표시한다.
영향력 없는 항 무시
- 만약 (O(n^2 + 2n + 1)) 과 같은 계산이 나왔다면 (O(n^2)) 으로 표시한다.

시간 복잡도는 특정 크기의 입력(n)을 기준으로 실행하는 연산의 횟수이다. 다시 말해 연산 횟수를 세면 된다. 그렇다고 모든 실행 연산을 계산하는 것이 아니라 핵심적인 부분 만 계산하면 된다(빅오 표기법 특징상 가장 큰수(영향력이 가장 큰)만 생각하기 때문)

복잡도	소요 시간	예시
(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문, 삽입정렬, 버블 정렬, 선택 정렬
(O(C^n))	지수 시간	피보나치 수열

빅오 표기법

공간 복잡도는 알고리즘 실행에 메모리가 얼마나 사용되는지를 계산하면 된다. 예를 들어 크기가 n인 배열을 입력으로 주었을 때, 알고리즘이 n * n의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 (n^2) 이다.

빅오 표기법 공간 복잡도