[Algorithm] 시간 복잡도 & 공간 복잡도

❕ 시간 복잡도

입력에 대해 총 얼마나 오래 걸리는 지를 의미한다. 알고리즘이 진행되면서 연산되는 횟수이다.
빅오 표기법을 사용하여 표현하는데, 빠르게 증가하는 항만 고려하여 표기한다.

arr = [1, 2, 3, 4, 5]
sum = 0      

for i in arr:
    sum += i

print(sum)

N개의 입력을 받고 연산 횟수는 N에 비례하기 때문에, 시간 복잡도는 $O(N)$이다.
 

a = 5
b = 7
print(a + b)

한 번의 연산만 하기 때문에 시간 복잡도는 $O(1)$이다
 

arr = [3, 5, 1, 2, 4]

for i in arr:
    for j in arr:
    	print(i + j)

N개의 입력을 받고 N X N만큼의 연산이 필요하기 때문에 시간 복잡도는 $O(N^2)$이다.
 
$O(1)$  <  $O(logN)$  <  $O(N)$  <  $O(NlogN)$  <  $O(N^2)$  <  $O(N^3)$  <  $O(2^N)$  
 
[ 파이썬 내장 함수 시간 복잡도 ]
https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

 
보통 코딩 테스트에서는 연산 횟수가 10억이 넘어가도록 작성하면 시간 초과로 통과하지 못한다.

	N이 1000일 때의 연산 횟수
$O(N)$	1000
$O(NlogN)$	10,000
$O(N^2)$	1,000,000
$O(N^3)$	1,000,000,000

 

• N의 범위가 500인 경우 : 시간 복잡도가 $O(N^3)$ 인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우 : $O(N^2)$
• N의 범위가 100,000인 경우 : $O(NlogN)$
• N의 범위가 10,000,000인 경우 : $O(N)$

---

❕ 공간 복잡도

메모리의 사용 기준은 MB기준이다.
코딩 테스트에서도 메모리 제한이 있기 때문에, 데이터에 대한 효율적인 처리가 요구된다.

• int a[1000] : 4KB
• int a[1000000] : 4MB
• int a[2000][2000] : 16MB

보통 데이터의 개수가 1000만 단위가 넘어가지 않아야 한다고 한다.!