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

여기에 쓰세요

A bilibili vedio도 이것을 보여줍니다: [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] 좋은 vedio라고 생각하지만 언어는 중국어입니다.

시간 복잡도

• 시간 복잡도는 무엇을 의미하나요?

• 시간 복잡도는 입력 크기에 따라 알고리즘을 실행하는 데 걸리는 시간을 측정한 것입니다. 알고리즘의 효율성을 설명하는 방법으로, 서로 다른 알고리즘을 비교하여 어느 알고리즘이 가장 효율적인지 판단하는 데 사용됩니다.

• 시간 복잡도를 어떻게 계산하나요?

• 시간 복잡도를 계산하려면 알고리즘이 수행하는 작업 수를 입력 크기의 함수로 고려해야 합니다. 작업 횟수를 측정하는 가장 일반적인 방법은 특정 작업이 수행된 횟수를 세는 것입니다.

• 시간 복잡도를 계산할 때 흔히 저지르는 실수는 무엇입니까?

• 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)

또는 파이썬 방식으로 작성합니다:

def find_largest_n(nums, n):
    if n  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  heap[largest]:
        largest = left

    if 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  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  heap[largest]:
        largest = left

    if 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은 크지 않다

힙q 사용: 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

내가 찾은 내용 및 개선 방법

n이 큰 경우 Sorted는 약간의 시간이 소요되지만(때로는 heapq를 사용하는 것보다 더 나음) Python Heapq은 많은 시간이 소요됩니다.

• Sorted에는 시간이 조금 걸리지만 Python Heapq에는 시간이 많이 걸리는 이유는 무엇입니까?
• sorted()는 Python에 내장된 함수이므로 이에 대한 Python 공식 문서를 찾을 수 있습니다.

내장된 함수는 컴파일 언어인 C로 작성되었기 때문에 heapq보다 빠릅니다.

• 어떻게 개선할 수 있나요?
• heapq.sort() 대신 내장 함수 sorted()를 사용하여 코드 성능을 향상시킬 수 있습니다. sorted() 함수는 Python에 내장된 함수로, C로 구현되므로 heapq.sort()
보다 훨씬 빠릅니다.

경련

대량 데이터를 처리할 때는 코드 성능을 향상시키기 위해 heapq.sort() 대신 내장 함수를 사용해야 합니다. 대용량 데이터를 다룰 때 시간 복잡도 문제에 주의해야 합니다. 때로는 시간 복잡성의 함정을 피할 수 없지만 가능한 한 이를 피하도록 노력해야 합니다.

나에 대해

안녕하세요 멍친위안 입니다. 저는 학생입니다. 나는 새로운 것을 배우는 것을 좋아합니다.
내 github을 볼 수 있습니다: [MengQinYuan의 Github][https://github.com/mengqinyuan]