알고리즘 복잡도

알고리즘 복잡도

알고리즘 복잡도는 시간 복잡도와 공간 복잡도 두 개로 구분이 된다. 

 

# 시간 복잡도 

시간 복잡도는 알고리즘의 입력 데이터에 대해 수행하는 연산 횟수의 총합을 나타내며, 대개는 입력 데이터의 크기에 대한 함수로 나타난다. 이 함수를 T(n)으료 표현할 때, 알고리즘의 시간 복잡도는 O(T(n))과 같이 표현이 된다. 여기서 O는 최악의 경우의 복잡도를 나타내는 빅오 표기법이다. 

 

빅오 외 표기법
빅 오메가 (Big Omega) 표기법 : Ω(n)
빅 오메가 표기법은 최악의 경우를 나타내는 빅오 표기법과 달리, 최선의 경우를 나타낸다. 즉, 알고리즘의 실행 시간이 최소한 이 정도 이상이라는 것을 나타낸다. 

빅세타 (Big Theta) 표기법 : Θ(n)
빅세타 표기법은 빅오 표기법과 빅 오메가 표기법을 합친 것으로 알고리즘의 실행 시간이 최악의 경우와 최선의 경우 모두 이 정도라는 것을 뜻 한다.

오메가 - 빅오 (Omega-Big O) 표기법 : ω(n) - O(n)
오메가-빅오 표기법은 빅 오메가 표기법과 빅오 표기법을 합친 것으로, 알고리즘의 실행 시간이 최선과 최악 중 적어도 하나의 경우는 이 정도, 나머지 경우는 저 정도라는 것을 나타낸다.

 

# 빅 오 표기법

알고리즘 시간 복잡도를 빅 오 표기법으로 나타낼 때 아래와 같은 형태로 표현이 된다. 

- O(1) 상수 시간 알고리즘:

• 대표적인 예시: 배열 인덱스로 접근, 상수 길이의 반복문
• 권장하는 입력 크기 범위 : 제한 없음

- O(log n) 로그 시간 알고리즘:

• 대표적인 예시: 이진 탐색
• 권장하는 입력 크기 범위: 1 ~ 10^18

- O(n) 선형 시간 알고리즘:

• 대표적인 예시: 배열 순회, 선형 검색
• 권장하는 입력 크기 범위: 1 ~ 10^6

- O(n log n) 선형 로그 시간 알고리즘:

• 대표적인 예시: 병합 정렬, 퀵 정렬
• 권장하는 입력 크기 범위: 1 ~ 10^6

- O(n^2) 이차 시간 알고리즘:

• 대표적인 예시: 선택 정렬, 삽입 정렬
• 권장하는 입력 크기 범위: 1 ~ 10^3

- O(n^3) 삼차 시간 알고리즘:

• 대표적인 예시: 행렬 곱셈
• 권장하는 입력 크기 범위: 1 ~ 100

- O(2^n) 지수 시간 알고리즘:

• 대표적인 예시: 완전 탐색, 비트마스크
• 권장하는 입력 크기 범위: 1 ~ 20

 

# 상수항 표기법

시간 복잡도에서 상수항은 무시되기 때문에 O(2n)과 O(n)은 동일한 시간 복잡도를 갖는다. 따라서, O(2n) 대신에 O(n)으로 표기하는 것이 일반적이다.

 

이러한 현상이 일어나는 이유는 알고리즘의 시간 복잡도는 입력 크기에 따라 연산 횟수가 증가하는 비율을 나타내는데, 상수항은 입력 크기와 무관하게 일정한 값이기 때문에 시간 복잡도에 영향을 미치지 않는다. 

 

예를 들어, 만약 입력 크기 n에 대해서 알고리즘의 시간 복잡도가 2n^2 + 3n + 1 이라면, O(2n^2 + 3n + 1)은 O(n^2)로 간략화가 된다. 여기서 2는 상수항으로 무시되고, 가장 높은 차수인 n^2에 대한 항만을 남기기 때문이다. 

 

# 공간 복잡도

공간 복잡도는 알고리즘이 수행하는 동안 사용하는 메모리 양을 나타내며, 대개는 입력 데이터의 크기에 대한 함수로 나타낸다. 이 함수를 S(n)으로 표현할 때, 알고리즘의 공간 복잡도는 O(S(n))과 같이 표현한다.

알고리즘의 성능을 평가할 때, 시간 복잡도와 공간 복잡도는 모두 중요한 요소이다. 하지만 일반적으로는 시간 복잡도가 더 중요하며, 특히 대용량 데이터에 대한 처리 시간이 중요한 경우에는 시간 복잡도를 우선 고려된다.