「時間の複雑さの落とし穴に注意してください」
時間の複雑さの落とし穴に注意してください
ここに書いてください
bilibili vedio にもこれが表示されます: [Bilibili Video][https://www.bilibili.com/video/BV16u4m1c7cU/?spm_id_from=333.999.0.0] これは良い vedio だと思いますが、言語は中国語です。
時間の複雑さ
- 時間計算量とは何を意味しますか?
時間計算量は、入力サイズの関数としてアルゴリズムの実行にかかる時間を測定します。これはアルゴリズムの効率を記述する方法であり、さまざまなアルゴリズムを比較し、どれが最も効率的であるかを判断するために使用されます。
時間計算量の計算方法
時間計算量を計算するには、アルゴリズムによって実行される演算の数を入力のサイズの関数として考慮する必要があります。操作の数を測定する最も一般的な方法は、特定の操作が実行された回数をカウントすることです。
時間計算量を計算する際によくある落とし穴は何ですか?
- 入力サイズを考慮しない: アルゴリズムによって実行される操作の数だけを考慮すると、時間の複雑さを過小評価する可能性があります。たとえば、ループの実行回数を数えても、入力のサイズを考慮しない場合、時間計算量が高すぎる可能性があります。
- アルゴリズムの効率を考慮していない: 一部のアルゴリズムは、入力サイズが小さい場合でも多くの演算を実行する可能性があり、これにより時間の複雑さが高くなる可能性があります。たとえば、バブル ソートや選択ソートなどのソート アルゴリズムは、小さな配列内の 2 つの要素を交換するだけで済む場合でも、二次時間計算量を持ちます。
- アルゴリズムの最悪のシナリオを考慮していない: 一部のアルゴリズムには、最悪のシナリオよりも少ない操作を実行する最良のシナリオがあります。たとえば、二分探索のような検索アルゴリズムには、対数時間でターゲット要素を見つけるという最良のシナリオがありますが、配列内のすべての要素を調べる必要があるという最悪のシナリオもあります。
時間計算量の例をいくつか見てみましょう
ここに質問があります:
リスト内の最大 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: 並べ替えを使用する
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 <= 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は大きくない
ヒープクを使用: 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 サイトの他の関連記事を参照してください。

ホットAIツール

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

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

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

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

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











Pythonは、データサイエンス、Web開発、自動化タスクに適していますが、Cはシステムプログラミング、ゲーム開発、組み込みシステムに適しています。 Pythonは、そのシンプルさと強力なエコシステムで知られていますが、Cは高性能および基礎となる制御機能で知られています。

PythonはゲームとGUI開発に優れています。 1)ゲーム開発は、2Dゲームの作成に適した図面、オーディオ、その他の機能を提供し、Pygameを使用します。 2)GUI開発は、TKINTERまたはPYQTを選択できます。 TKINTERはシンプルで使いやすく、PYQTは豊富な機能を備えており、専門能力開発に適しています。

Pythonは学習と使用が簡単ですが、Cはより強力ですが複雑です。 1。Python構文は簡潔で初心者に適しています。動的なタイピングと自動メモリ管理により、使いやすくなりますが、ランタイムエラーを引き起こす可能性があります。 2.Cは、高性能アプリケーションに適した低レベルの制御と高度な機能を提供しますが、学習しきい値が高く、手動メモリとタイプの安全管理が必要です。

限られた時間でPythonの学習効率を最大化するには、PythonのDateTime、時間、およびスケジュールモジュールを使用できます。 1. DateTimeモジュールは、学習時間を記録および計画するために使用されます。 2。時間モジュールは、勉強と休息の時間を設定するのに役立ちます。 3.スケジュールモジュールは、毎週の学習タスクを自動的に配置します。

Pythonは開発効率でCよりも優れていますが、Cは実行パフォーマンスが高くなっています。 1。Pythonの簡潔な構文とリッチライブラリは、開発効率を向上させます。 2.Cのコンピレーションタイプの特性とハードウェア制御により、実行パフォーマンスが向上します。選択を行うときは、プロジェクトのニーズに基づいて開発速度と実行効率を比較検討する必要があります。

PythonListSarePartOfThestAndardarenot.liestareBuilting-in、versatile、forStoringCollectionsのpythonlistarepart。

Pythonは、自動化、スクリプト、およびタスク管理に優れています。 1)自動化:OSやShutilなどの標準ライブラリを介してファイルバックアップが実現されます。 2)スクリプトの書き込み:Psutilライブラリを使用してシステムリソースを監視します。 3)タスク管理:スケジュールライブラリを使用してタスクをスケジュールします。 Pythonの使いやすさと豊富なライブラリサポートにより、これらの分野で優先ツールになります。

Pythonを1日2時間学ぶだけで十分ですか?それはあなたの目標と学習方法に依存します。 1)明確な学習計画を策定し、2)適切な学習リソースと方法を選択します。3)実践的な実践とレビューとレビューと統合を練習および統合し、統合すると、この期間中にPythonの基本的な知識と高度な機能を徐々に習得できます。
