[😸코테] 시간복잡도 VS 공간복잡도

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리나?

 

빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법

예제) 5개의 데이터를 받아 차례로 5회 더해준다 -> 연산횟수가 N에 비례함 -> O(N)이라 표기

array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5)
summary = 0 # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary += x

# 결과를 출력
print(summary)

예제) 2중 반복문 -> N*N만큼의 연산 사용 -> O(N^2)

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

for i in array:
	for j in array:
    	temp = i*j
        print(temp)

코딩테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다.

 

시간복잡도표 

위쪽에 있을수록 더 빠르다.

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^N)	지수 시간

제한 시간이 1초인 경우의 예시

N의 범위	시간 복잡도
500	O(N^3)
2000	O(N^2)
100,000	O(NlogN)
10,000,000	O(N)

 

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하나?

공간 복잡도 또한 빅오 표기법을 사용한다.

시간 복잡도에서의 절대적인 제한이 1초인 것처럼 메모리 사용량 기준은 보통 128~512MB 정도로 제한한다.

 

시간과 메모리 측정

import time

start_time = time.time() # 측정 시작
end_time = time.time()
print("time :", end_time - start_time) # 수행 시간 출력