検索
ホームページバックエンド開発Python チュートリアル「時間の複雑さの落とし穴に注意してください」

“Be wary of time complexity pitfalls

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

ここに書いてください

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: 並べ替えを使用する

sort 関数を使用するソリューションは次のとおりです:

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
ヒープクを使用: 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 公式ドキュメントを見つけることができます。

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

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

脳震盪

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

私について

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

以上が「時間の複雑さの落とし穴に注意してください」の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
Python:主要なアプリケーションの調査Python:主要なアプリケーションの調査Apr 10, 2025 am 09:41 AM

Pythonは、Web開発、データサイエンス、機械学習、自動化、スクリプトの分野で広く使用されています。 1)Web開発では、DjangoおよびFlask Frameworksが開発プロセスを簡素化します。 2)データサイエンスと機械学習の分野では、Numpy、Pandas、Scikit-Learn、Tensorflowライブラリが強力なサポートを提供します。 3)自動化とスクリプトの観点から、Pythonは自動テストやシステム管理などのタスクに適しています。

2時間でどのくらいのPythonを学ぶことができますか?2時間でどのくらいのPythonを学ぶことができますか?Apr 09, 2025 pm 04:33 PM

2時間以内にPythonの基本を学ぶことができます。 1。変数とデータ型を学習します。2。ステートメントやループの場合などのマスター制御構造、3。関数の定義と使用を理解します。これらは、簡単なPythonプログラムの作成を開始するのに役立ちます。

プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は?プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は?Apr 02, 2025 am 07:18 AM

10時間以内にコンピューター初心者プログラミングの基本を教える方法は?コンピューター初心者にプログラミングの知識を教えるのに10時間しかない場合、何を教えることを選びますか...

中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか?中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか?Apr 02, 2025 am 07:15 AM

fiddlereveryversings for the-middleの測定値を使用するときに検出されないようにする方法

Python 3.6にピクルスファイルをロードするときに「__Builtin__」モジュールが見つからない場合はどうすればよいですか?Python 3.6にピクルスファイルをロードするときに「__Builtin__」モジュールが見つからない場合はどうすればよいですか?Apr 02, 2025 am 07:12 AM

Python 3.6のピクルスファイルのロードレポートエラー:modulenotFounderror:nomodulenamed ...

風光明媚なスポットコメント分析におけるJieba Wordセグメンテーションの精度を改善する方法は?風光明媚なスポットコメント分析におけるJieba Wordセグメンテーションの精度を改善する方法は?Apr 02, 2025 am 07:09 AM

風光明媚なスポットコメント分析におけるJieba Wordセグメンテーションの問題を解決する方法は?風光明媚なスポットコメントと分析を行っているとき、私たちはしばしばJieba Wordセグメンテーションツールを使用してテキストを処理します...

正規表現を使用して、最初の閉じたタグと停止に一致する方法は?正規表現を使用して、最初の閉じたタグと停止に一致する方法は?Apr 02, 2025 am 07:06 AM

正規表現を使用して、最初の閉じたタグと停止に一致する方法は? HTMLまたは他のマークアップ言語を扱う場合、しばしば正規表現が必要です...

Investing.comの反クローラーメカニズムをバイパスするニュースデータを取得する方法は?Investing.comの反クローラーメカニズムをバイパスするニュースデータを取得する方法は?Apr 02, 2025 am 07:03 AM

Investing.comの反クラウリング戦略を理解する多くの人々は、Investing.com(https://cn.investing.com/news/latest-news)からのニュースデータをクロールしようとします。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

SecLists

SecLists

SecLists は、セキュリティ テスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティ テスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティ テストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジング ペイロード、機密データ パターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテスト マシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい