[CodingTest] 이코테 기초 - 복잡도

1. 복잡도 (complexity)

• 알고리즘의 성능을 나타내는 척도

 

(1) 시간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는가
• 알고리즘을 위해 필요한 연산의 횟수

 

(2) 공간 복잡도

• 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는가
• 알고리즘을 위해 필요한 메모리의 양

 

(3) 빅오(Big-O)

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

 

Big-O 표기법	명칭	속도
O(1)	상수 시간	↑ 빠름 ​ ​ ​ ↓ 느림
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^N)	지수 시간

2. 시간 측정

• 수행 시간 측정 코드

import time
start_time = time.time() #시작 시간

#실행코드 

end_time = time.time() #종료 시간
print("수행 시간 : ", end_time-start_time)