[알고리즘 이론] 시간 복잡도와 공간 복잡도

복잡도란, 

1. 알고리즘의 성능, 효율성을 나타내는 척도
2. 알고리즘의 사용 시간 및 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준 
3. 빅오(O), 오메가(Ω), 세타(Θ) 표기법 등이 잇다.

 

 

빅-오(Big-O) 표기법 

최악의 경우를 나타냅니다.

즉, 알고리즘을 실행 했을 때 최대로 걸릴 수 있는 시간을 나타냅니다. 

 

O(1): n이 증가하여도 실행 시간은 동일한 알고리즘 (EX, 기본 연산 수)

O(log n): 연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (EX, 이진 탐)

O(n): n의 값이 증가함에 따라 선형적으로 증가하는 알고리즘 (EX, 1중 for)

O(n log n): O(n)의 알고리즘과 O(log n)의 알고리즘이 중첩된 형태 (EX, 퀵 정렬)

O(n^2): O(n)의 알고리즘과 O(log n)의 알고리즘이 중첩된 상태 (EX, 삽입/버블/선택 정렬)

O(2^n): 가장 느린 시간 복잡도로 주로 재귀적으로 수행하는 알고리즘 (EX, 피포나치 수열)

 

 

시간 복잡도

시간 복잡도는 특정 크기의 입력에 따른 연산의 횟수입니다.

같은 값을 출력하는 경우에도 어떤 알고리즘을 사용했는지, 알고리즘을 어떻게 작성하였는지에 따라 다른 시간복잡도를 얻을 수 있습니다. 

시간 복잡도가 낮은 알고리즘이 효율적입니다.

 

- 최선의 경우
 = 최적의 값을 입력한 후, 작업을 완료하는데 가장 연산 횟수가 적은 경우
- 최악의 경우
 = 최악의 값을 입력한 후, 작업을 완료하는데 가장 연산 횟수가 높은 경우
- 평균의 경우
 = 여러 경우에 수를 입력한 후, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

알고리즘 활용 시 최악의 경우를 가장 많이 활용합니다.

 

 

공간 복잡도

공간 복잡도는 프로그램 실행과 완료에 필요한 메모리 공간을 나타냅니다. 

값이 같더라도, 어떤 자료구조를 사용했냐와 어떤 알고리즘을 사용했냐에 따라서 공간 복잡도는 달라질 수 있습니다. 

 

1. 알고리즘과 무관한 공간 (고정 공간)
  - 코드가 저장되어 있다. 알고리즘 실행을 위해 필요한 시스템이 들어간 공간. 

2. 알고리즘과 밀접한 공간 (가변 공간)
   - 변수가 저장되어 있다. 사용자가 작성한 알고리즘에 따라 사용되는 공간