시간복잡도 (Python)

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.

 

그래서 시간 복잡도는 코딩테스트를 풀 때 어떤 알고리즘을 사용할지에 대한 선택의 기준이 된다.

 

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

연산 횟수와 수행 시간을 고려하여 어떤 알고리즘을 써야할지 생각해 볼 수 있다.

 

물론, 시간 복잡도만으로 어떻게 문제를 풀지 선택하는 것은 아니지만

데이터의 갯수에 따라 시간 복잡도를 계산할 줄 알면 써야하는 알고리즘의 범위를 좁힐 수 있게 된다.

 

 

 

시간 복잡도 표기법

 

시간 복잡도를 정의하는 3가지 유형이 있다.

 

빅-오메가  Ω(n)	최선일 때(best case)의 연산 횟수를 나타낸 표기법
빅-세타  θ(n)	보통일 때(average case)의 연산 횟수를 나타낸 표기법
빅-오  O(n)	최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

예를 들어 아래와 같이 1~100 사이의 랜덤값을 찾아 출력하는 코드가 있다면

import random

findNumber = random.randrange(1, 101)

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

빅-오메가 Ω(n) 표기법의 시간 복잡도는 1 이다.

빅-세타 θ(n) 표기법의 시간 복잡도는 50 = N/2 이다.

빅-오 O(n) 표기법의 시간 복잡도는 100 = N 이다.

 

코딩 테스트에서는 다양한 테스트 케이스를 통과해야하니 최악일 때의 연산 횟수를 나타내는

빅-오 O(n) 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.

 

 

시간 복잡도는 데이터의 크기(N)에 따라 수행 시간이 달라진다.

아래 그래프를 보면 데이터의 크기가 클수록 각각의 시간 복잡도 간의 차이가 커진다.

 

이미지 출처 : Do it! 알고리즘 코딩 테스트 파이썬 - 시간복잡도

 

 

 

 

 

 

 

시간 복잡도 활용하기

 

1.  알고리즘 선택의 기준으로 시간 복잡도 사용하기

 

N개의 수가 주어졌을 때 이를 오름차순으로 정렬하는 문제가 있다고 해보자. (1 ≤ N ≤ 1,000,000 / 시간 제한 2초)

 

파이썬에서는 1초에 2,000만 번 ~ 1억 번의 연산이 가능하다고 예측할 수 있는데 최악의 경우를 생각해야하니

1초에 2,000만 번의 연산이 가능하다고 하면 제한 시간이 2초이기 때문에 연산 횟수가 4,000만번 이하여야 문제를 해결할 수 있다.

 

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

 

예를 들어 이 문제를 버블 정렬로 푼다고 할 때 버블정렬의 시간 복잡도는 O(n^2)이므로 연산 횟수는

1,000,000 ^ 2 = 1,000,000,000,000이고 이는 40,000,000보다 훨씬 크다.

따라서 버블 정렬은 이 문제에 부적합한 알고리즘이라고 판단할 수 있다.

 

그럼 병합 정렬로 이 문제를 푼다고 할 때 병합 정렬의 시간 복잡도는 O(nlogn)이므로 연산 횟수는

1,000,000 * log2(1,000,000) =  약 20,000,000이고 이는 40,000,000보다 작으므로 적합한 알고리즘이라고 판단할 수 있다.

 

이와 같이 시간 복잡도를 분석해보면 문제를 푸는데 적합한 알고리즘을 선택할 수 있다.

 

 

 

 

 

2.  시간 복잡도를 바탕으로 코드 로직 개선하기

 

시간 복잡도 도출 기준

 

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

→  3N  =  N + 10  =  N 으로 취급한다.

 

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

 

 

위 기준을 따라 시간 초과가 발생하였을 때 문제가 되는 부분을 찾아내어 코드를 개선할 수 있다.

 

 

 

 

 

 

참고 자료

🔗 [하루코딩]  알고리즘 코딩테스트 핵심이론 강의 - 시간복잡도 (Python)