출처
동빈나 이코테
참고
파이썬 자료형

⚛️ 복잡도 (Complexity)

시간 복잡도 - 알고리즘 수행 시간
공간 복잡도 - 알고리즘의 메모리 사용량

🦄 시간 복잡도

• 코딩테스트 문제의 시간제한은 대략 5초
• Python이 초당 2000만번의 연산만 가능하다고 가정하는 것이 좋음
  • 5초에 1억번

🦄 빅오 표기법(Big-O Notation)

차수가 가장 큰 항만 남기는 것

3N³ + 5N² + 1,000,000
시간복잡도 O(N³)

🦄 연산 횟수에 따른 시간 복잡도

연산 횟수가 5억

• C언어 - 1~3초
• Python - 5~15초
  • PyPy는 때로 C보다 빠름

O(N³), N=5000

• 연산 횟수가 1250억
  • Python은 약 2500초

🦄 시간제한에 따른 알고리즘 설계

N의 max	빅오
500 (5백)	O(N³)
2,000 (2천)	O(N²)
100,000 (10만)	O(NlogN)
10,000,000 (천만)	O(N)

🦄 수행 시간 측정 코드

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

# 프로그램 소스코드
end_time = time.time()		# 측정 종료
print('time:', end_time - start_time)	# 수행 시간 출력