時間の複雑さの落とし穴に注意してください

ここに書いてください

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)

または、Python の方法で記述します:

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) であることはほとんどの人が知っています。

最初の解決策は 2 番目の解決策よりも優れているようです。しかし、Python ではそうではありません。

最終コードを見てください:

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は大きくない

ヒープクを使用: 0.002430099993944168
Python ヒープq: 0.06343129999004304
ソート済み : 9.280000813305378e-05
n = 910
ヒープクを使用: 9.220000356435776e-05
Python ヒープq: 0.07715500006452203
ソート済み : 9.360001422464848e-05
n = 920
ヒープクを使用: 9.440002031624317e-05
Python ヒープq: 0.06573969998862594
ソート済み: 0.00012450001668184996
n = 930
ヒープクを使用: 9.689992293715477e-05
Python ヒープq: 0.06760239996947348
ソート済み : 9.66999214142561e-05
n = 940
ヒープqを使用: 9.600003249943256e-05
Python ヒープq: 0.07372559991199523
ソート済み : 9.680003859102726e-05
n = 950
ヒープクを使用: 9.770004544407129e-05
Python ヒープq: 0.07306570000946522
ソート済み: 0.00011979998089373112
n = 960
ヒープクを使用: 9.980006143450737e-05
Python ヒープq: 0.0771204000338912
ソート済み: 0.00022829999215900898
n = 970
ヒープクを使用: 0.0001601999392732978
Python ヒープq: 0.07493270002305508
ソート済み: 0.00010840001050382853
n = 980
ヒープクを使用: 9.949994273483753e-05
Python ヒープq: 0.07698320003692061
ソート済み: 0.00010300008580088615
n = 990
ヒープクを使用: 9.979994501918554e-05
Python ヒープq: 0.0848745999392122
ソート済み: 0.00012620002962648869

n が大きい場合は?

n = 10000
ヒープクを使用: 0.003642000025138259
Python ヒープq: 9.698883199947886
ソート済み: 0.00107999995816499
n = 11000
ヒープクを使用: 0.0014836000045761466
Python ヒープq: 10.537632800056599
ソート済み: 0.0012236000038683414
n = 12000
ヒープクを使用: 0.001384599949233234
Python ヒープq: 12.328411899972707
ソート済み: 0.0013226999435573816
n = 13000
ヒープクを使用: 0.0020017001079395413
Python ヒープq: 15.637207800056785
ソート済み: 0.0015075999544933438
n = 14000
ヒープクを使用: 0.0017026999266818166
Python ヒープq: 17.298848500009626
ソート済み: 0.0016967999981716275
n = 15000
ヒープクを使用: 0.0017773000290617347
Python ヒープq: 20.780625900020823
ソート済み: 0.0017105999868363142

気づいたこととそれを改善する方法

n が大きい場合、Sorted には少し時間がかかります (場合によっては heapq を使用するよりも良い場合もあります) が、Python Heapq には多くの時間がかかります。

• Sorted には少し時間がかかるのに、Python Heapq には時間がかかるのはなぜですか?
• sorted() は Python の組み込み関数であるため、それに関する Python 公式ドキュメントを見つけることができます。

Bulit-in 関数はコンパイル言語である C で記述されているため、heapq よりも高速です。

• どうすれば改善できますか?
• heapq.sort() の代わりに組み込み関数sorted() を使用すると、コードのパフォーマンスを向上させることができます。 sorted() 関数は Python の組み込み関数であり、C で実装されているため、heapq.sort()
よりもはるかに高速です。

脳震盪

大きなデータを扱う場合は、コードのパフォーマンスを向上させるために、 heapq.sort() の代わりに組み込み関数を使用する必要があります。大規模なデータを扱うときは、時間の複雑さの落とし穴に注意する必要があります。場合によっては、時間計算量の落とし穴が避けられないこともありますが、できるだけ回避するように努めるべきです。

私について

こんにちは、mengqinyuanです。私は学生です。新しいことを学ぶのが大好きです。
私の github をご覧ください: [MengQinYuan の Github][https://github.com/mengqinyuan]