시간 복잡도란?
주어진 문제를 해결하기 위한 연산 횟수
일반적으로 파이썬 프로그램에서는 2,000만 번 ~ 1억 번의 연산을 1초의 수행시간으로 예측 할 수 있음
시간 복잡도 정의
- 빅 - 오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수
- 빅 - 세타(Θ(n)) : 보통일 때(average case)의 연산 횟수
- 빅 - 오(Ο(n)) : 최악일 때(worst case)의 연산 횟수
코드예제
import random
findNumber = random.randrange(1,101) #1~100까지 랜덤값 생성
for i in range(1,101):
if i == findNumber:
print(i)
break
# 빅 - 오메가 : 1번
# 빅 - 세타 : 50번 (N/2)
# 빅 -오 : 100번 (N)
코딩테스트와 시간 복잡도
빅 - 오 표기법을 기준으로 수행시간 계산하자
시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다름
마무리
코딩 테스트 준비를 하면서 시간 복잡도를 고려하는 게 언제나 스트레스다....친해질겸 정리해봤다...
'🏷️CS > Algorithm' 카테고리의 다른 글
[백준] 구현 1157 / 4673 / 1316 (0) | 2023.05.09 |
---|---|
코테에 사용하기 좋은 라이브러리 기능 (0) | 2023.04.30 |
[백준] 1253 (좋다) (1) | 2023.03.01 |
[백준] 1940 (주몽) (0) | 2023.03.01 |
[백준] 2018(수들의 합5) (0) | 2023.02.25 |