Big O 記法 - Python

1. 定義

アルゴリズムの実行時間またはスペース使用量の上限を記述する数学的表記。これは O(f(n)) として表されます。f(n) は、入力 n のサイズの関数として時間または空間を表す関数です。 .

詳細については、http://bigocheatsheet.com

をご覧ください。

2. 目的

• アルゴリズムの比較: さまざまなアルゴリズムを比較し、特定の問題に対して最も効率的なアルゴリズムを選択できます。
• スケーラビリティ: データ量が増加したときにアルゴリズムがどのように動作するかを予測するのに役立ちます。

3. 複雑さの分析

• 最悪のケース: アルゴリズムに時間がかかるか、より多くのリソースを使用するシナリオを指します。 Big O は通常、このケースを指します。
• 最良ケースと平均ケース: 重要ではありますが、Big O 表記ではあまり使用されません。

4. 宇宙 vs.時間

• 時間的複雑さ: アルゴリズムの実行にかかる時間を指します。
• スペースの複雑さ: 使用される追加メモリの量を指します。 O(1) (定数空間) または O(n) (線形空間) のような表記を使用できます。

例:

import timeit
import matplotlib.pyplot as plt
import cProfile

# O(1)


def constant_time_operation():
    return 42

# O(log n)


def logarithmic_time_operation(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

# O(n)


def linear_time_operation(n):
    total = 0
    for i in range(n):
        total += i
    return total

# O(n log n)


def linear_logarithmic_time_operation(n):
    if n 



<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173189059010897.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Notación Big O - Python"></p>

<p>単純に大きな表記法を適用するだけでは十分ではないこと、または、これは最初のステップではありますが、メモリを最適化する他の方法があることを覚えておいてください。たとえば、<strong>スロット</strong>、キャッシュ、スレッド、並列処理、プロセスなど</p>

<p>読んでいただきありがとうございます!!<br>
反応したり、意見を述べたりして私をサポートしてください。</p>


          

            
        

以上がBig O 記法 - Pythonの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。