규도자 개발 블로그

파이썬(Python) 내장함수의 시간복잡도 본문

Python/Python

파이썬(Python) 내장함수의 시간복잡도

규도자 (gyudoza) 2019. 4. 29. 21:42

파이썬(Python) 내장함수의 시간복잡도

나는 내장함수는 뭔가 당연히 최적화돼있겠거니 하고 생각없이 쓰곤 한다. 하지만 그런 자세가 프로그램의 효율에 커다란 영향을 끼치지 않나 싶다. 특히 이번에 에라토스테네스의 체를 응용한 문제를 풀고 있는데 정확한 개념을 알기 위해 위키에 쳐보니 다음과 같은 함수가 나왔다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우 
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

출처를 보니 JSON'S CODE BLOG라는 곳에서 오일러의 10번 문제를 푼 알고리즘을 그대로 차용하였다. (오일러의 10번 문제는 10보다 작은 소수의 합은 17이다. 그러면 200만 이하의 모든 소수의 합은 얼마인가?이다.) 대충 에라토스테네스의 체에 대한 설명만 보고 스스로 생각했을 때는 range함수를 이용해서 하나의 배열을 만든 다음에 조건에 해당하는 숫자만 해당 배열에서 찾아 없애는 식으로 쉽게 생각했었는데 보면 알겠지만 실제로 구현된 상태는 그와는 약간 다른 형태를 취하고 있다.


에라토스 테네스의 체의 진행을 애니메이션으로 구현한 모습. 출처는 역시 위키피디아이다.


 바로 여기에서 파이썬 내장함수에 대한 시간복잡도를 고려했느냐에 대한 차이가 나온다. 이곳은 파이썬 내장함수에 대한 시간복잡도가 정리돼있는 사이트이다. 만약 내가 생각한대로 구현했다면 삭제해야 하는 값, 그러니까 예를 들어 2가 주어졌을 때 그 숫자의 배수에 해당하는 값이 올 때마다 주어진 배열에서 찾아 삭제해야 한다. 위 사이트에서 list에 대한 시간복잡도를 보면 알겠지만 효율이 O(n)이다.



나는 그냥 쉽게 구현하려는 생각만으로 훨씬 더 효율 좋게 만들 수 있는 함수를 최소 O(n^2)이상의 시간복잡도를 갖는 형태로 구현할 뻔 했다. 반성하는 마음에 남긴다. 위 사이트도 어떤 기능을 구현하는 데에 참고하면 좋을 것이다.

Comments