アルゴリズムの複雑さとBigO表記

アルゴリズムの複雑さ、特にアルゴリズムのコンテキストでそれを測定する方法について説明しましょう。

解決する問題が同じで入力が同じ場合、アルゴリズムが異なれば、問題の解決にかかる時間も異なります。

時には、特に管理する必要のある要素の数が増えるにつれて、大きく異なる時間が発生します。

この複雑さはビッグオー、大文字を使用する他の理由はありませんo慣例としての手紙:O(n)O(1)等々。

表示されるBigOの最も一般的な測定値は、効率の高いものから低いものの順に並べ替えられています。

  • O(1)
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n^2)
  • O(n!)

どこn入力の数です。たとえば、2つのアイテムを並べ替える必要がある場合nは2で、20.000アイテムを並べ替える必要がある場合は、n20.000です。

ただし、の値を置き換える必要はありませんO()計算。これはシンボルであり、開発者やアルゴリズムを検討しているすべての人にその効率を知らせることを目的としています。

とのアルゴリズムO(1)効率は私たちが見つけることができる最高のものです。実行時間は入力の数に依存せず、実行には常に同じ時間がかかります

とのアルゴリズムO(n)はかり線形に入力の数で。 10個のアイテムの場合は1秒かかり、100個のアイテムの場合は10秒かかります。

とのアルゴリズムO(n^2)、4アイテムの場合は16秒かかり、10アイテムの場合は100秒かかります。

次のレッスンでは、多数のアルゴリズムのBigO効率を分析および計算します。

Big O表記は、アルゴリズムが他のアルゴリズムよりも高速であるかどうかを判断するために必要なすべての情報を提供するわけではないことに注意することが重要です。特に、BigO値が同じ場合はそうです。この場合、効率をテストするために他のツールを使用する必要があります。

ただし、アルゴリズムのクラスが異なる場合(O(n)vsO(n^2)たとえば)、間違いありません。