[Do it! 알고리즘 코딩테스트 with Python] 시간복잡도

시간복잡도

다음 시간 복잡도 예제를 통해 '빅오메가, 빅세타, 빅오'에 대해서 알아보자면 다음과 같다.

import random
findNumber = random.randrange(1, 101)

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

 

빅오메가(Ω(n))

- 최선일 때(best case)의 연산 횟수를 나타낸 표기법

- 시간복잡도:  1 (findNumber로 1을 생각하고 있었는데, i가 1부터 시작할 수 있으니까 바로 값을 찾았기 때문)

 

빅세타(θ(n))

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

- 시간복잡도: N/2 = 50

 

빅오(O(n))

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

- 시간복잡도: N

- 코딩테스트 준비 시 빅오법으로 볼 것! 즉, 최악을 생각하면서 문제를 풀어나갈 것

---

파이썬은 1초에 2000만 번 계산을 한다고 한다. 그럼 시간 제한이 2분이라고 하면 4000만 번 계산하는 것이다.

어떤 정렬하는 문제에서 1<N<1,000,000 이라는 조건이 있을 때 최악인 1,000,000을 각각 버블 정렬 시간 복잡도와 병합 정렬 시간 복잡도에 넣어 계산하여 알고리즘을 찾는 것이 중요하다. (참고로,  버블 정렬의 시간복잡도는 O(n²), 병합 정렬 의 시간복잡도는 O(nlog(n))임)

 

즉, 가장 먼저 시간복잡도를 도출할 수 있어야 하며, 그에 맞는 알고리즘, 코드 로직 개선이 필요하다는 의미이다.