[이코테] 복잡도

동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

1_  시간 복잡도(Time Complexity)

'얼마나 오래 걸리는지' → 연산 횟수

 

# 빅오(Big-O) 표기법

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

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

(시간 복잡도 표에서 위쪽에 있을수록 더 빠름)

 

코딩테스트 문제를 풀기전에 조건을 보면 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있다.

예를 들어, 시간 제한 1초인 문제에 데이터의 개수 N이 1000만개를 넘어가면 O(N)의 시간 복잡도로 동작하는 알고리즘을 설계하면 문제를 풀 수 있다.

 

2_  공간 복잡도(Space Complexity)

'얼마나 많은 메모리를 차지하는지' → 메모리의 양

 

코딩테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다.

즉, 일반적인 경우 데이터의 개수가 1000만 단위를 넘어가지 않게끔 알고리즘을 설계해야 한다.

 

3_ 시간 측정

import time

s_time = time.time() 
## 시간 측정할 소스 코드
e_time = time.time()

print("수행 시간 :",  e_time - s_time)

 

 

 

⚠️ 해당 글은 '이것이 코딩 테스트다 with 파이썬 <저자_ 나동빈>' 책을 공부하고 복습하기 위해 작성했습니다.