[Python] 시간 복잡도 표기법 알아보기

알고리즘 공부를 시작해 보도록 하겠다.

주언어가 C++이었는데 파이썬이 요즘 추세이면서 AI에 주로 쓰이기 때문에 익숙해지기 위해서 선택하였다.

과연 성공적으로 적응할 수 있을 것인지~~ 파이팅~~!~!

 

먼저 알고리즘 공부를 시작하기 전 시간 복잡도에 대해 공부해보자.

 

시간 복잡도

주어진 문제를 해결하기 위한 연산 횟수로 파이썬에서는 일반적으로 2000만번 ~ 1억 번의 연산을 1초의 수행 시간으로 본다.

 

( C++에서는 보통 1억 번의 연산을 1초로 배웠었다. )

 

시간 복잡도 유형

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

· 빅-세타($theta$(n)): 평균일 때(average case)의 연산 횟수를 나타낸 표기법

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

 

1~100 사이의 값을 무작위로 출력하는 코드를 보고 시간 복잡도 유형에 따라 시간 복잡도를 찾아보자. 

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

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

 

· 빅-오메가($Omega$(n)): 1

· 빅-세타($theta$(n)): N/2

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

 

코테에서는 빅-오를 기준으로 수행 시간을 계산하는 것이 좋다. 아무래도 최악일 때를 기준으로 삼아서 문제를 풀어야지 어떠한 테케도 넘어갈 수 있기 때문이다.

빅-오 표기법의 시간 복잡도

x를 데이터 크기라고 했을 때 x가 증가할수록 성능이 다르다는 것을 확인할 수 있다. 

 

백준 2750번 문제를 예를 들어 설명하자.

제한시간이 2초라는 것은 4,000번 이하의 연산 횟수로 문제를 해결해야한다는 뜻이고 이를 통해서 어떤 정렬 알고리즘을 사용해야할지 판단해야한다. 

 

버블 정렬 : $N^2$

병합 정렬 : $Nlog(N)$

 

따라서 데이터 크기 N을 통해서 사용해야하는 알고리즘을 추측할 수 있다.

 

시간 복잡도 도출 기준

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

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

 

N = 100000
num = 1

for i in range(N):
  print("연산 횟수 " + str(num))
  num += 1

 

연산 횟수: N

 

N = 100000
num = 1

for i in range(N):
  print("연산 횟수 " + str(num))
  num += 1
  
for i in range(N):
  print("연산 횟수 " + str(num))
  num += 1
  
for i in range(N):
  print("연산 횟수 " + str(num))
  num += 1

 

연산 횟수: 3N

 

하지만 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도는 O(n)으로 같다.

 

N = 100000
num = 1

for i in range(N):
  for j in rnage(N):
    print("연산 횟수 " + str(num))
    num += 1

 

연산 횟수: $N^2$

시간 복잡도: $O(n^2)$

 

만약 일반 for 문이 더 있더라도 가장 많이 중첩된 반복문을 기준으로 도출하므로 $N^2$으로 유지된다.

 

 

출처: Do it! 알고리즘 코딩 테스트 - 파이썬 편