[복잡도] 시간 복잡도 / 공간 복잡도

1. 알고리즘 복잡도 계산이 필요한 이유

하나의 문제를 푸는 알고리즘은 다양할 수 있음
  - 정수의 절대값 구하기
    - 1, -1 ->> 1
    - 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기
    - 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기

> 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

> 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

 

2. 알고리즘 성능 표기법

- Big O (빅-오) 표기법: O(N)
  - 알고리즘 최악의 실행 시간을 표기
  - **가장 많이/일반적으로 사용함**
  - **아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문**

- Ω (오메가) 표기법:  Ω(N)
  - 오메가 표기법은 알고리즘 최상의 실행 시간을 표기

- Θ (세타) 표기법: Θ(N)
  - 오메가 표기법은 알고리즘 평균 실행 시간을 표기

 

시간 복잡도

• 알고리즘 실행 속도
• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지
• 일반적인 코딩 테스트에서는 상수를 고려해야 하는 경우는 적지만, 이처럼 빅오 표기법이 항상 절대적인 것은 아니다
•  프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문. 입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함
• 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨 

3. 대문자 O 표기법

* O(입력)
  - 입력 n 에 따라 결정되는 시간 복잡도 함수
  - 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
      - 만약 시간 복잡도 함수가 2$n^2$ + 3n 이라면
      - 가장 높은 차수는 2$n^2$ 
      - 상수는 실제 큰 영향이 없음 
      - 결국 빅 오 표기법으로는 O($n^2$) (서울부터 부산까지 가는 자동차의 예를 상기)

 

빠름

빅오 표기법	명칭	N이 1,000일 때의 연산 횟수	알고리즘 가능한 N의 범위	알고리즘 종류
O(1)	상수 시간 (1번 연산)			인접행렬?, 해쉬테이블
O(logN) = log2N	로그 시간			이분탐색, 이진탐색트리, 힙
O(N)	선형 시간 (N만큼 연산)	1,000	10,000,000 이하	삽입정렬(정렬O), 계수정렬, 완전탐색, 메모이제이션, 위상정렬, 인접리스트?, BFS, 이진탐색트리(최악)
O(NlogN)	로그 선형 시간	10,000	100,000 이하	퀵정렬(정렬X), 정렬라이브러리, 다익스트라, 크루스칼
O(N^2)	이차 시간	1,000,000	2,000 이하	선택정렬, 삽입정렬(정렬X), 퀵정렬(정렬O), TopDown
O(V+M(1+log_{2-M/V}V)		10,000,000		서로소 집합
O(N^3)	삼차 시간	1,000,000,000	500 이하	플로이드워셜
O(2^n)	지수 시간
O(N!)

느림

 

 

공간 복잡도

- 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
- 총 필요 저장 공간
  - 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  - 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
  - S(P) = c + S_p(n)
    - c: 고정 공간
    - S_p(n) : 가변 공간

> 빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우됨

> 데이터의 개수가 1,000만 단위가 넘어가지 않도록 해야 함

 

[공간 복잡도 계산]
- 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 됨 
  - 이를 빅 오 표기법으로 표현할 수 있으면 됨 

 

[공간 복잡도 대략적인 계산은 필요함]
- 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음
- 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음
- 또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우도 있음

Complexity:
- expected worst-case time complexity: O(N)
- expected worst-case space complexity: O(N)

> 현업에서 최근 빅데이터를 다룰 때는 저장 공간을 고려해서 구현을 하는 경우도 있음 

 

int a[1000] 		#4KB
int a[1000000] 		#4MB
int a[2000][2000] 	#16MB

 

[공간 복잡도 예제1]
- n! 팩토리얼 구하기
  - n! = 1 x 2 x ... x n
- n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요함
- 공간 복잡도는 O(1)
> 공간 복잡도 계산은 실제 알고리즘 실행시 사용되는 저장공간을 계산하면 됨

def factorial(n):
    fac = 1
    for index in range(2, n + 1):
        fac = fac * index
    return fac

 

[공간 복잡도 예제2]
- n! 팩토리얼 구하기
  - n! = 1 x 2 x ... x n
- 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 됨
  - factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
- 공간 복잡도는 O(n)

def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1

 

시간과 메모리 측정

import time

start_time = time.time()
#코드
end_time = time.time()

print("time :", end_time - start_time)