BigO表記の実用的なJavaの例

投稿日: 2019-10-18 2022-10-18
タグ: Algorithms, Java

1. 概要

このチュートリアルでは、何について話します BigO表記は意味します。コードの実行時間への影響を調査するために、いくつかの例を見ていきます。

2. BigO表記の直感

BigONotationを使用して記述されたアルゴリズムのパフォーマンスをよく耳にします。

アルゴリズムのパフォーマンス、またはアルゴリズムの複雑さの研究は、アルゴリズム分析の分野に分類されます。アルゴリズム分析は、ディスクスペースや時間など、アルゴリズムが消費するリソースの数に関する質問に答えます。

時間をリソースとして見ていきます。通常、アルゴリズムの完了にかかる時間は短いほど良いです。

3. 定数時間アルゴリズム– O（1）

アルゴリズムのこの入力サイズは、その実行時間にどのように影響しますか？ Big Oを理解するための鍵は、物事が成長する可能性のある速度を理解することです。ここで問題となる速度は、入力サイズあたりの所要時間です。

この単純なコードを考えてみましょう。

int n = 1000;
System.out.println("Hey - your input is: " + n);

明らかに、上記のnが何であるかは問題ではありません。このコードの実行には一定の時間がかかります。 nのサイズには依存しません。

同様に：

int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);

上記の例も一定時間です。実行に3倍の時間がかかる場合でも、は入力のサイズnに依存しません。定数時間アルゴリズムを次のように表します： O（1）。 O（2）、 O（3）、さらには O（1000）も同じ意味であることに注意してください。

実行にかかる時間は正確には気にせず、一定の時間がかかるだけです。

4. 対数時間アルゴリズム– O（log n）

定数時間アルゴリズムは（漸近的に）最速です。 対数時間は次に速いです。残念ながら、想像するのは少し難しいです。

対数時間アルゴリズムの一般的な例の1つは、二分探索アルゴリズムです。 Javaでバイナリ検索を実装する方法については、ここをクリックしてください。

ここで重要なのは、実行時間が入力の対数に比例して増加することです（この場合、基数2に対数します）：

for (int i = 1; i < n; i = i * 2){
    System.out.println("Hey - I'm busy looking at: " + i);
}

n が8の場合、出力は次のようになります。

Hey - I'm busy looking at: 1
Hey - I'm busy looking at: 2
Hey - I'm busy looking at: 4

単純なアルゴリズムはlog（8）=3回実行しました。

5. 線形時間アルゴリズム– O（n）

対数時間アルゴリズムの後、次に速いクラスである線形時間アルゴリズムを取得します。

何かが直線的に成長すると言う場合、それはその入力のサイズに正比例して成長することを意味します。

単純なforループを考えてみてください。

for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
}

これはforループで何回実行されますか？ n 回です！これが実行されるのにどれくらいの時間がかかるか正確にはわかりません–そしてそれについて心配する必要はありません。

私たちが知っていることは、上に示した単純なアルゴリズムは、その入力のサイズに比例して大きくなるということです。

（1000n + 1000）よりも 0.1n の実行時間をお勧めしますが、どちらも線形アルゴリズムです。それらは両方とも、入力のサイズに比例して直接成長します。

繰り返しますが、アルゴリズムが次のように変更された場合：

for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
    System.out.println("Hmm.. Let's have another look at: " + i);
    System.out.println("And another: " + i);
}

ランタイムは、入力のサイズnで線形のままです。線形アルゴリズムを次のように表します： O（n）。

定数時間アルゴリズムと同様に、ランタイムの詳細は気にしません。 O（2n + 1）はO（n）と同じです。これは、BigONotationが入力サイズの増加に関係しているためです。

6. N Log N時間アルゴリズム– O（n log n）

n log nは、次のクラスのアルゴリズムです。実行時間は、入力の n lognに比例して増加します。

for (int i = 1; i <= n; i++){
    for(int j = 1; j < n; j = j * 2) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
}

たとえば、 n が8の場合、このアルゴリズムは 8 * log（8）= 8 * 3 =24回実行されます。 forループに厳密な不等式があるかどうかは、BigO表記法では関係ありません。

7. 多項式時間アルゴリズム– O（np）

次は、多項式時間アルゴリズムです。これらのアルゴリズムは、 n lognアルゴリズムよりもさらに低速です。

多項式という用語は、2次（n2）、3次（n3）、4次（n4）などを含む一般的な用語です。機能。 知っておくべき重要なことは、O（n2）はO（n4）よりも速いO（n3）よりも速いということです。

二次時間アルゴリズムの簡単な例を見てみましょう。

for (int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
}

このアルゴリズムは82=64回実行されます。別のforループをネストすると、これは O（n3）アルゴリズムになることに注意してください。

8. 指数時間アルゴリズム– O（ k n）

今、私たちは危険な領域に入っています。これらのアルゴリズムは、入力サイズによって指数化されたいくつかの要因に比例して増加します。

たとえば、 O（2n）アルゴリズムは、入力が追加されるたびに2倍になります。したがって、 n = 2 の場合、これらのアルゴリズムは4回実行されます。 n = 3 の場合、8回実行されます（対数時間アルゴリズムの反対のようなものです）。

O（3n）アルゴリズムは、入力が追加されるたびに3倍になり、 O（kn）アルゴリズムは、入力が追加されるたびにk倍大きくなります。

O（2n）時間アルゴリズムの簡単な例を見てみましょう。

for (int i = 1; i <= Math.pow(2, n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

このアルゴリズムは28=256回実行されます。

9. 階乗時間アルゴリズム– O（n！）

ほとんどの場合、これはそれが得るのと同じくらい悪いです。このクラスのアルゴリズムの実行時間は、入力サイズの階乗に比例します。

この典型的な例は、ブルートフォースアプローチを使用してトラベリングセールスマンの問題を解決することです。

巡回セールスマン問題の解決策の説明は、この記事の範囲を超えています。

代わりに、前のセクションのように、単純な O（n！）アルゴリズムを見てみましょう。

for (int i = 1; i <= factorial(n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

ここで、 factorial（n）は単にn！を計算します。 nが8の場合、このアルゴリズムは実行されます 8！ = 40320 回数。

10. 漸近関数

Big Oは、漸近関数として知られているものです。これはすべて、限界でのアルゴリズムのパフォーマンスに関係していることを意味します。 –大量の入力がスローされたとき。

Big Oは、アルゴリズムが小さなサイズの入力でどれだけうまく機能するかを気にしません。これは、大量の入力に関係しています（100万個の数値のリストを並べ替えることを考えてください。 5つの数字のリストを並べ替えます）。

もう1つの注意点は、他の漸近関数があることです。BigΘ（シータ）とBigΩ（オメガ）はどちらも限界でのアルゴリズムを記述します（限界これは単に膨大な入力の場合）。

これらの3つの重要な関数の違いを理解するには、まず、Big O、BigΘ、およびBigΩのそれぞれが set （つまり、要素のコレクション）を記述することを知る必要があります。

ここで、私たちのセットのメンバーはアルゴリズムそのものです。

Big Oは、特定の速度（上限）よりも悪くない実行されるすべてのアルゴリズムのセットを表します
逆に、BigΩは、特定の速度（下限）よりも良くないを実行するすべてのアルゴリズムのセットを表します
最後に、BigΘは、を特定の速度で実行するすべてのアルゴリズムのセットを記述します（同等のようです）

上記の定義は数学的に正確ではありませんが、理解に役立ちます。

通常、Big O を使用して説明されていることを聞くことができますが、BigΘとBigΩについて知っていても問題はありません。

11. 結論

この記事では、Big O表記法と、アルゴリズムの複雑さを理解することがコードの実行時間にどのように影響するかについて説明しました。

さまざまな複雑さのクラスの優れた視覚化がここにあります。

いつものように、このチュートリアルのコードスニペットはGitHubのにあります。

getdocs

13036