(파이썬) 점근 표기법

알고리즘의 실행 시간과 입력 규모의 관계를 말할 때에는 점근 표기법이라는 것을 공식적으로 사용한다.

점근 표기법은 입력 규모가 무한대로 갈 때의 알고리즘의 복잡도를 의미한다.

# 점근 표기법
def f(x):
    ans = 0
    for i in range(1000): # Loop that takes constant time
        ans += 1
    print('Number of additions so far', ans)

    for i in range(x): # Loop that takes time x
        ans += 1
    print('Number of additions so far', ans)

    for i in range(x): # Nested loops take time x**2
        for j in range(x):
            ans += 1
            ans += 1
    print('Number of additions so far', ans)
    return ans


print(f(2))

위의 코드를 보면 각 줄의 코드를 실행할 때 한 단위의 시간이 걸린다고 가정한다면 이 함수의 실행 시간은 1000 + x + 2x^2로 표현할 수 있다. 상수 1000은 첫 번째 반복문이 실행되는 횟수에 해당한다. x는 두 번째 반복문이 실행되는 횟수에 해당한다. 마지막으로 2x^2는 중첩된 반복문에 있는 두 개의 문장을 실행한 것에 해당한다.

만약 f(2)을 호출한다면 다음과 같이 출력된다.

Number of additions so far 1000
Number of additions so far 1002
Number of additions so far 1010
1010