알고리즘 복잡도 - 시간 복잡도

1. 시간 복잡도 표기법

빅-오메가(Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법

빅-세타(𝚯(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법

빅-오(O(n)): 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

import random
findNumber = random.randrange(1,101) # 1~100 사이의 랜덤값 생성

for i in range(1,101):
	if i == findNumber:
		print(i)
		break

예제 코드의 시간복잡도는

빅-오메가(Ω(n)) : 1번

빅-세타(𝚯(n)): N/2번

빅-오(O(n)): N번

 

코딩 테스트에서는 빅-오를 기준으로 수행 시간을 계산하는 것이 좋다. 실제 테스트에서는 1개의 테스트 케이스로 합격 여부를 결정하지 않는다. 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야 합격으로 판단하므로, 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야한다.

 

 

2. 시간 복잡도 활용하기

알고리즘 선택의 기준으로 사용하기!

 

(예시) 버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n^2), O(nlog{n}) 이라고 알고 있다고 가정하고 알고리즘 복잡도를 계산해 보겠다.

연산 횟수 계산 방법 : 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

알고리즘 적합성 평가 (예시) 시간 제한은 2초이고, 4,000만번 이하의 연산 횟수로 문제를 해결해야 한다고 하자.

버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 > 40,000,000 → 부적합 알고리즘

병합 정렬 = 1,000,000\log_2{(1,000,000)} = 약 20,000,000 < 40,000,000 → 적합 알고리즘

 

 

3. 시간 복잡도 도출 기준

1) 상수는 시간 복잡도 계산에서 제외한다

2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다

 

 

출처 : Do it! 알고리즘 코딩 테스트(python)