'시간 복잡도 함정에 주의하세요\'-파이썬 튜토리얼-php.cn

“Be wary of time complexity pitfalls

시간 복잡도 함정에 주의하세요

여기에 쓰세요

한 빌리빌리 비디오에도 이런 내용이 나와 있습니다: [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] 좋은 비디오인 것 같은데 언어가 중국어예요.

시간 복잡도

시간 복잡도는 무엇을 의미하나요?
시간 복잡도는 입력 크기에 따라 알고리즘이 실행되는 데 걸리는 시간을 측정한 것입니다. 알고리즘의 효율성을 설명하는 방법으로, 서로 다른 알고리즘을 비교하여 어떤 알고리즘이 가장 효율적인지 판단하는 데 사용됩니다.
시간복잡도는 어떻게 계산하나요?
시간 복잡도를 계산하려면 알고리즘이 수행하는 작업 수를 입력 크기의 함수로 고려해야 합니다. 작업 횟수를 측정하는 가장 일반적인 방법은 특정 작업이 수행된 횟수를 세는 것입니다.
시간 복잡도를 계산할 때 흔히 저지르는 실수는 무엇입니까?
1. 입력 크기를 고려하지 않음: 알고리즘이 수행하는 작업 수만 고려하면 시간 복잡도를 과소평가할 수 있습니다. 예를 들어, 루프가 실행되는 횟수를 계산하지만 입력 크기를 고려하지 않으면 시간 복잡도가 너무 높아질 수 있습니다.
1. 알고리즘의 효율성을 고려하지 않음: 일부 알고리즘은 입력 크기가 작더라도 많은 작업을 수행할 수 있어 시간 복잡도가 높아질 수 있습니다. 예를 들어, 버블 정렬 및 선택 정렬과 같은 정렬 알고리즘은 작은 배열에서 두 요소만 교체하면 되지만 2차 시간 복잡도를 갖습니다.
1. 알고리즘의 최악의 시나리오를 고려하지 않음: 일부 알고리즘에는 최악의 시나리오보다 더 적은 작업을 수행하는 최상의 시나리오가 있습니다. 예를 들어 이진 검색과 같은 검색 알고리즘에는 로그 시간 내에 대상 요소를 찾는 최상의 시나리오가 있지만 배열의 모든 요소를 검사해야 하는 최악의 시나리오가 있습니다.

시간 복잡도의 몇 가지 예를 살펴보겠습니다.

여기 질문이 있습니다:
목록에서 최대 10개의 정수를 찾으세요.

import random
ls = [random.randint(1, 100) for _ in range(n)]

로그인 후 복사

테스트 기능은 다음과 같습니다.

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

로그인 후 복사

해결 방법 1: 힙 사용

heapq 모듈을 사용하는 솔루션은 다음과 같습니다.

def find_max_n(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

로그인 후 복사

또는 Python 방식으로 작성합니다.

def find_largest_n(nums, n):
    if n <= 0:
        return []

    max_heap = []

    for num in nums:
        if len(max_heap) < n:
            max_heap.append(num)
            # call sift_down
            for i in range((len(max_heap) - 2) // 2, -1, -1):
                _sift_down(max_heap, i)
        elif num > max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left < len(heap) and heap[left] > heap[largest]:
        largest = left

    if right < len(heap) and heap[right] > heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)

로그인 후 복사

해결 방법 2: 정렬 사용

정렬 기능을 사용하는 솔루션은 다음과 같습니다.

def find_max_n(ls, n):
    return sorted(ls, reverse=True)[:n]

로그인 후 복사

힙의 시간 복잡도는 O(n log k)이고 정렬 기능의 시간 복잡도는 O(n log n)라는 사실은 대부분의 사람들이 알고 있습니다.

첫 번째 솔루션이 두 번째 솔루션보다 나은 것 같습니다. 하지만 파이썬에서는 그렇지 않습니다.

최종 코드 보기:

import time
def benchmark(func, *args) -> float:
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    return end - start

def find_max_n_heapq(ls, n):
    import heapq
    return heapq.nlargest(n, ls)

def find_max_n_python_heap(nums, n):
    if n <= 0:
        return []

    max_heap = []

    for num in nums:
        if len(max_heap) < n:
            max_heap.append(num)
            # call sift_down
            for i in range((len(max_heap) - 2) // 2, -1, -1):
                _sift_down(max_heap, i)
        elif num > max_heap[0]:
            max_heap[0] = num
            _sift_down(max_heap, 0)

    return max_heap

def _sift_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left < len(heap) and heap[left] > heap[largest]:
        largest = left

    if right < len(heap) and heap[right] > heap[largest]:
        largest = right

    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        _sift_down(heap, largest)


def find_max_n_sorted(ls, n):
    return sorted(ls, reverse=True)[:n]

# test
import random
for n in range(10, 10000, 100):
    ls = [random.randint(1, 100) for _ in range(n)]
    print(f"n = {n}")
    print(f"Use    Heapq: {benchmark(find_max_n_heapq, ls, n)}")
    print(f"Python Heapq: {benchmark(find_max_n_python_heap, ls, n)}")
    print(f"Sorted      : {benchmark(find_max_n_sorted, ls, n)}")

로그인 후 복사

Python3.11 VScode에서 실행했는데 결과는 다음과 같습니다.

n은 크지 않다

Heapq 사용: 0.002430099993944168
Python 힙q: 0.06343129999004304
정렬 : 9.280000813305378e-05
n = 910
Heapq 사용: 9.220000356435776e-05
Python 힙q: 0.07715500006452203
정렬 : 9.360001422464848e-05
n = 920
Heapq 사용: 9.440002031624317e-05
Python 힙q: 0.06573969998862594
정렬 : 0.00012450001668184996
n = 930
Heapq 사용: 9.689992293715477e-05
Python 힙q: 0.06760239996947348
정렬 : 9.66999214142561e-05
n = 940
Heapq 사용: 9.600003249943256e-05
Python 힙q: 0.07372559991199523
정렬 : 9.680003859102726e-05
n = 950
Heapq 사용: 9.770004544407129e-05
Python 힙q: 0.07306570000946522
정렬 : 0.00011979998089373112
n = 960
Heapq 사용: 9.980006143450737e-05
Python 힙q: 0.0771204000338912
정렬 : 0.00022829999215900898
n = 970
Heapq 사용: 0.0001601999392732978
Python 힙q: 0.07493270002305508
정렬 : 0.00010840001050382853
n = 980
Heapq 사용: 9.949994273483753e-05
Python 힙q: 0.07698320003692061
정렬 : 0.00010300008580088615
n = 990
Heapq 사용: 9.979994501918554e-05
Python 힙q: 0.0848745999392122
정렬 : 0.00012620002962648869

n이 크면?

n = 10000
Heapq 사용: 0.003642000025138259
Python 힙q: 9.698883199947886
정렬 : 0.00107999995816499
n = 11000
Heapq 사용: 0.0014836000045761466
Python 힙q: 10.537632800056599
정렬 : 0.0012236000038683414
n = 12000
Heapq 사용: 0.001384599949233234
Python 힙q: 12.328411899972707
정렬 : 0.0013226999435573816
n = 13000
Heapq 사용: 0.0020017001079395413
Python 힙q: 15.637207800056785
정렬 : 0.0015075999544933438
n = 14000
Heapq 사용: 0.0017026999266818166
Python 힙q: 17.298848500009626
정렬 : 0.0016967999981716275
n = 15000
Heapq 사용: 0.0017773000290617347
Python 힙q: 20.780625900020823
정렬 : 0.0017105999868363142