파이썬 시간 복잡도 (Big-o, 빅오)

코드 동작 실행 시간을 체크하는 데 사용한다. 가장 기본적인 생각은 코드가 실행된 순간부터 끝나는 순간을 체크하면 된다.

파이썬은 time이라는 라이브러리를 사용하면 쉽게 볼 수 있다.

 

import time

start = time.time()  # 실행될 때 찍힌 시간

for i in range(10000000):
    pass

end = time.time()  # 실행될 때 찍힌 시간

print(f"{end - start}")  # 정수부는 초단위, 소수부는 마이크로 초단위

출력
0.47263002395629883

 

time.time은 이 코드가 실행될 때 시작하는 시간이다. 그러니 시작과 끝에 이 코드를 적으면 얼마나 동작했는지 알 수 있다. 하지만 이런 코드에는 문제가 있다. 왜냐면 객관적인 시간이 아니기 때문이다. 컴퓨터의 스펙에 따라 다르게 나오기 때문에 객관적인 지표가 필요했다.

 

그래서 여러 방법이 나왔지만 가장 대표적인 BIg-O를 사용한다. 연산의 횟수를 기반으로 실행시간을 체크한다. 점근 표기법이라는 최고차 항의 차수만 고려하는 표기법을 이용하여 나타낸다. 최고 차 항만 고려하는 이유는 낮은 차수들은 비교적 무시할 수 있기 때문이다. 100,000,000+100 이면 100을 상대적으로 무시하는 것과 같다. 

 

Big-O의 수학적 정의는 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n >= n0에 대하여 절댓값(f(n)) <= c * 절댓값(g(n)) 을 만족하는 상수 c와 n0가 존재하면 f(n = O(g(n))이다. 함수의 상한을 표시한다.

예를 들어보자 n >=5 이면 2n+1 < 10n 이므로 2n+1 = O(n), (이때 c = 10, n0 = 5이다)

 

예시 가정 

 

우리가 제곱을 해주는 코드를 만든다고 가정해보자 여러 방법이 있을 텐데 3가지 정도 예를 들어보며 시간 복잡도를 측정해보자. 

척도는 대입(몇 번 입력해야 하나), 뎃셈, 곱셈, 나눗셈으로 평가한다.

 

예시 1 

 

result = n*n

대입 : 1
덧셈 : 0
곱 : 1
나눗셈 : 0
합 : 2
시간 복잡도 : 2

 

예시 2

 

result = 0
for i in range(1, n+1):
    result += n

대입 : n+1
덧셈 : n
곱셈 : 0
나눗셈 : 0
합 : 2n+1
시간 복잡도 : n

 

시간 복잡도는 n이다. 왜냐면 최고 차 항만 보기 때문이다.

 

예시 3

 

result = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        result += 1

대입 : n*n+1
덧셈 : n*n
곱셈 : 0
나눗셈 : 0
합 : 2n**2+1
시간 복잡도 : n**2

 

얘가 시간 복잡도가 제일 높다. 이렇게 연산의 횟수에 기반하여 시간 복잡도를 측정하는데 제일 간단하고 작게 나올 수 있도록 해주는 게 알고리즘과 자료구조다.