[Algorithm & Other Concepts] 복잡도와 빅오(Big-O) 표기법

🦀 복잡도

복잡도
시간 복잡도	공간 복잡도
알고리즘 수행에 필요한 연산 횟수	알고리즘 수행에 필요한 메모리 양

-  복잡도가 낮을수록 좋은 알고리즘

 

-  시간 복잡도와 공간 복잡도는 거래 관계 ( = Trade-off )

 

-  Memoization ( = 메모이제이션 ) 

:  메모리 사용양을 늘림으로써 알고리즘 수행 시간을 대폭 줄이는 방법

 

---

 

🦀 시간 복잡도과 빅오(Big-O) 표기법

빅오(Big-O) 표기법

함수의 상한을 나타내는 표기법

 

-  시간 복잡도 ==  O(N)

-  N  =  처리할 데이터 개수 =  연산 횟수

-  여기서 '연산'이란 언어에서 지원하는 비교, 사칙 연산을 모두 포함한 개념

 

ex)

x = 1
y = 2

print(x + y)

-->  해당 예시에서의 시간 복잡도는 O(1)

 

-  빅오 표기법에 따른 명칭 정리

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

 

---

 

🦀 시간 및 메모리 측정

import time

# 측정 시작
start_time = time.time()

# 알고리즘 코드

# 측정 종료
end_time = time.time()

# 측정한 시간 확인
print("소요 시간: ", end_time - start_time)