[Python] 알고리즘 요구사항 분석 (시간 복잡도)

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

⚛️ 복잡도 (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)	# 수행 시간 출력

좋은 웹페이지 즐겨찾기