[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) # 수행 시간 출력
Author And Source
이 문제에 관하여([Python] 알고리즘 요구사항 분석 (시간 복잡도)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jehjong/Python-알고리즘-요구사항-분석-시간-복잡도저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)