시간 복잡도

시간 복잡도란?

주어진 문제를 해결하기 위한 연산 횟수

일반적으로 파이썬 프로그램에서는 2,000만 번 ~ 1억 번의 연산을 1초의 수행시간으로 예측 할 수 있음

시간 복잡도 정의

1. 빅 - 오메가(Ω(n)) :  최선일 때(best case)의 연산 횟수
2. 빅 - 세타(Θ(n)) : 보통일 때(average case)의 연산 횟수
3. 빅 - 오(Ο(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)의 증가에 따라 성능(수행 시간)이 다름 

 

마무리

코딩 테스트 준비를 하면서 시간 복잡도를 고려하는 게 언제나 스트레스다....친해질겸 정리해봤다...