1概要

このチュートリアルでは、

Big O表記が何を意味するのかについて説明します。いくつかの例を挙げて、コードの実行時間に与える影響を調べます。


2 Big O記法の直感

私たちはしばしばBig O記法を使って記述されたアルゴリズムの性能をよく耳にします。

アルゴリズムのパフォーマンス – あるいはアルゴリズムの複雑さ – の研究はhttps://en.wikipedia.org/wiki/Analysis

of

algorithms[algorithm analysis]の分野に入ります。アルゴリズム分析は、ディスク容量や時間など、アルゴリズムが消費するリソースの数に関する質問に答えます。

私たちは時間を資源として見ているでしょう。通常、アルゴリズムが完了するのにかかる時間が短いほど、より良いです。


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(2)



O(3)

、さらには

O(1000)

が同じことを意味することに注意してください。

実行にかかる時間を正確に気にする必要はなく、一定の時間がかかるだけです。


4対数時間アルゴリズム –

O(log n)


定時間アルゴリズムは(漸近的に)最も速いものです。

対数時間が次に早い

残念ながら、想像するのは少し面倒です

対数時間アルゴリズムの一般的な例の1つは、https://en.wikipedia.org/wiki/Binary

search

algorithm[binary search]アルゴリズムです。 Javaでバイナリ検索を実装する方法を見るには、リンク:/java-binary-search[ここをクリック]

ここで重要なことは、実行時間は入力の対数に比例して増加することです(この場合、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

において、依然として線形です。線形アルゴリズムを次のように表します。

コンスタントタイムアルゴリズムと同様に、ランタイムの詳細については気にしません。 Big O表記は入力サイズの増加に関係するため、


O(2n 1)



O(n)


と同じです。


6. N Log N時間アルゴリズム –

O(n log n)



  • n log n

    は次のクラスのアルゴリズムです** 実行時間は入力の

    n log n

    に比例して増加します。

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

たとえば、

n

が8の場合、このアルゴリズムは

8

log(8)= 8

3 = 24

回実行します。 forループに厳密な不等式があるかどうかは、Big O表記のためには無関係です。


7. 多項式時間アルゴリズム –

O(n ^ p ^)


次に多項式時間アルゴリズムを得ました。これらのアルゴリズムは、n log n__アルゴリズムよりもさらに遅くなります。

多項式という用語は、二次

(n ^ 2 ^)

、三次

(n ^ 3 ^)

、四次

(n ^ 4 ^)

などの関数を含む一般的な用語です。 ** 知っておくべき重要なことは、

O(n ^ 2 ^)



O(n ^ 3 ^)

より速いということです。

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

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);
    }
}

このアルゴリズムは

8 ^ 2 ^ = 64

回実行されます。別のforループを入れ子にした場合、これは

O(n ^ 3 ^)

アルゴリズムになります。


8指数時間アルゴリズム –


_O(


k

^ n ^)_


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

たとえば、


O(2 ^ n ^)

アルゴリズムは、追加の入力ごとに倍増します。

したがって、

n = 2

の場合、これらのアルゴリズムは4回実行されます。 __n = 3の場合、それらは8回実行されます(対数時間アルゴリズムの逆のようなものです)。


  • O(3 ^ n ^)

    アルゴリズムは入力が追加されるたびに3倍になり、

    O(k ^ n ^)

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


O(2 ^ n ^)

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

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

このアルゴリズムは

2 ^ 8 ^ = 256

回実行されます。


9階乗時間アルゴリズム –

O(n!)


ほとんどの場合、これは得られるものと同じくらい悪いものです。このクラスのアルゴリズムは、入力サイズのhttps://en.wikipedia.org/wiki/Factorial[factor]に比例した実行時間を持ちます。

これの典型的な例は、それを解決するために力ずくのアプローチを使用してhttps://en.wikipedia.org/wiki/Travelling

salesman

problem[traveling salesman]問題を解決することです。

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

代わりに、前のセクションのように、単純な

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の数字のリストをソートするのがよいでしょう)。

もう一つ注意すべきことは、

他の漸近関数があることです。

BigΘ(theta)とBigΩ(ω)も両方とも極限でのアルゴリズムを記述しています。

これら3つの重要な関数の違いを理解するために、まずBig O、BigΘ、BigΩのそれぞれが

set

(つまり、要素の集合)を記述していることを知る必要があります。

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

  • Big Oは、aよりも悪くない__を実行するすべてのアルゴリズムのセットを表します。

一定の速度(上限です)
** 逆に、BigΩは__noを実行するすべてのアルゴリズムのセットを表します。

一定の速度を上回る(下限です)
** 最後に、BigΘは

at

aを実行するすべてのアルゴリズムのセットを表します。

一定のスピード(平等のようです)

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

  • 通常、Big O ** を使用して説明されていることが聞こえますが、BigΘとBigΩについて知っても構いません。


11結論

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


http://bigocheatsheet.com/

[複雑なクラスのさまざまなクラスを視覚化したものがここにあります。

いつものように、このチュートリアルのコードスニペットはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[over on GitHub]にあります。