「Big O」表記法のわかりやすい英語の説明は何ですか? 質問する

Question

簡単に言うと、私の答えは間違いなく混乱を招くでしょうビッグオー表記(上限) と Big Theta 表記の "Θ" (両側の境界) を組み合わせます。しかし、私の経験では、これは実際には非学術的な環境での議論の典型です。混乱を招いた場合はお詫び申し上げます。

BigOh の複雑さは、次のグラフで視覚化できます。

Big Oh 表記法の最も簡単な定義は次のとおりです。

Big Oh 表記法は、アルゴリズムの複雑さを相対的に表したものです。

この文には、重要かつ意図的に選ばれた単語がいくつかあります。

相対的:同じもの同士しか比較できません。算術乗算を行うアルゴリズムと整数のリストをソートするアルゴリズムを比較することはできません。しかし、算術演算 (1 つは乗算、もう 1 つは加算) を行う 2 つのアルゴリズムを比較すると、意味のあることがわかります。

表現: BigOh (最も単純な形式) は、アルゴリズム間の比較を単一の変数に減らします。その変数は、観察または仮定に基づいて選択されます。たとえば、ソートアルゴリズムは通常、比較操作 (2 つのノードを比較して相対的な順序を決定する) に基づいて比較されます。これは、比較が高価であることを前提としています。しかし、比較は安価でもスワップが高価である場合はどうなるでしょうか。比較が変わります。

複雑さ: 10,000 個の要素をソートするのに 1 秒かかる場合、100 万個の要素をソートするにはどのくらいの時間がかかりますか? この場合の複雑さは、他の何かに対する相対的な尺度です。

残りの部分を読んだら、戻って上記をもう一度読んでください。

BigOh の最も良い例は、算術演算を行うことだと私は考えています。2 つの数字 (123456 と 789012) を考えてみましょう。学校で習った基本的な算術演算は次の通りです。

追加;

減算;

乗算;そして

分割。

これらはそれぞれ操作または問題であり、これらを解決する方法をアルゴリズムと呼びます。

加算は最も簡単です。数字を右に並べて列に数字を加算し、加算の最後の数字を結果に書き込みます。その数字の「十の位」の部分は、次の列に繰り越されます。

これらの数字の加算がこのアルゴリズムで最もコストのかかる操作であると仮定しましょう。当然ながら、これら 2 つの数字を加算するには、6 桁を加算する必要があります (7 桁目を繰り上げる場合もあります)。100 桁の数字 2 つを加算する場合は、100 回の加算が必要です。10,000桁の数字2 つを加算する場合は、10,000 回の加算が必要です。

パターンがわかりますか?複雑さ(つまり演算の数) は、大きい数の桁数nに正比例します。これをO(n)または線形複雑さと呼びます。

減算も同様です (繰り上がりの代わりに借り入れが必要になる場合がある点が異なります)。

掛け算は異なります。数字を並べて、下の数字の最初の桁を取り、それを上の数字の各桁に順番に掛け算し、各桁ごとにこれを繰り返します。したがって、2 つの 6 桁の数字を掛け算するには、36 回の掛け算を行う必要があります。最終結果を得るには、10 回または 11 回もの列の加算を行う必要がある場合もあります。

100 桁の数字が 2 つある場合、10,000 回の乗算と 200 回の加算を行う必要があります。100 万桁の数字が 2 つある場合、1 兆 (10 ¹² ) 回の乗算と 200 万回の加算を行う必要があります。

アルゴリズムは n の 2乗でスケールするため、これはO(n ² )または二次の複雑度になります。ここで、もう 1 つの重要な概念を紹介します。

私たちが気にするのは、複雑さの最も重要な部分だけです。

^{賢明な人は、演算回数を n 2} + 2nと表せることに気付いたかもしれません。しかし、それぞれ 100 万桁の 2 つの数値の例からわかるように、2 番目の項 (2n) は重要ではなくなります (その段階では、演算回数全体の 0.0002% を占めることになります)。

ここでは最悪のシナリオを想定していることに気付くでしょう。6 桁の数字を掛け算する場合、一方が 4 桁でもう一方が 6 桁であれば、掛け算は 24 回だけです。それでも、その「n」の最悪のシナリオ、つまり両方が 6 桁の数字の場合を計算します。したがって、Big Oh 表記はアルゴリズムの最悪のシナリオに関するものです。

電話帳

次に思いつく例は電話帳です。通常はホワイトページなどと呼ばれますが、国によって異なります。ただし、ここでは姓、イニシャルまたは名、場合によっては住所、電話番号の順に人をリストしたものについてお話します。

さて、1,000,000 の名前が載っている電話帳から「John Smith」の電話番号を検索するようにコンピュータに指示するとしたら、どうしますか? S が何番目から始まるか推測できるという事実を無視して (推測できないと仮定しましょう)、どうしますか?

典型的な実装は、真ん中まで開いて、500,000 番目を取り^、それを「スミス」と比較することです。それがたまたま「スミス、ジョン」だった場合、それは本当に幸運でした。それよりずっと可能性が高いのは、「ジョンスミス」がその名前の前か後にあることです。それが後にある場合は、電話帳の最後の半分を半分に分割して繰り返します。それが前にある場合は、電話帳の最初の半分を半分に分割して繰り返します。以下同様に行います。

これはバイナリ検索と呼ばれ、気づいているかどうかにかかわらず、プログラミングで毎日使用されています。

したがって、100 万の名前が載っている電話帳から名前を見つけたい場合、この操作を最大 20 回実行すれば、実際に任意の名前を見つけることができます。検索アルゴリズムを比較する際に、この比較を「n」と決定します。

3 つの名前が記載された電話帳の場合、比較は最大 2 回必要です。

7 の場合は最大 3 かかります。

15の場合は4が必要です。

…

1,000,000 の場合は 20 かかります。

それは驚くほど良いことですよね？

BigOh の用語では、これはO(log n)または対数計算量です。ここで問題となる対数は、ln (底 e)、log ₁₀、log _{2 、またはその他の底である可能性があります。O(2n}² ) と O(100n ² ) がどちらも O(n ² ) であるのと同じように、O(log n) であることは問題ではありません。

ここで、BigOh を使用してアルゴリズムで次の 3 つのケースを判断できることを説明する価値があります。

最良のケース:電話帳検索では、最良のケースは 1 回の比較で名前を見つけることです。これはO(1)または一定の複雑さです。

予想されるケース:上で説明したように、これはO(log n)であり、

最悪の場合:これも O(log n) です。

通常、私たちは最良のケースを気にしません。私たちが関心があるのは、予想される最悪のケースです。場合によっては、これらのいずれかがより重要になることがあります。

電話帳に戻ります。

電話番号を持っていて、名前を見つけたい場合はどうすればよいでしょうか。警察には逆引き電話帳がありますが、そのような検索は一般人には許可されていません。それとも許可されているのでしょうか。技術的には、通常の電話帳で番号を逆引きできます。どのように行うのでしょうか。

まず最初の名前から始めて、番号を比較します。一致すれば素晴らしいですが、一致しなければ次の名前に進みます。電話帳は順序付けされていないため(電話番号順ではない)、このように行う必要があります。

電話番号から名前を検索するには（逆引き）次のようにします。

最良のケース: O(1);

予想されるケース: O(n) (500,000の場合)

最悪の場合: O(n) (1,000,000 の場合)。

巡回セールスマン

これはコンピュータサイエンスでは非常に有名な問題であり、言及する価値があります。この問題では、N 個の町があります。各町は、一定の距離の道路によって 1 つ以上の他の町と接続されています。巡回セールスマン問題は、すべての町を訪問する最短のツアーを見つけることです。

簡単そうに聞こえますか? もう一度考えてみてください。

3 つの町 A、B、C があり、すべての町の間に道路がある場合は、次のようにします。

A → B → C

A → C → B

B → C → A

B → A → C

C → A → B

C → B → A

まあ、実際には、これらのいくつかは同等なので、それより少ないです (たとえば、A → B → C と C → B → A は同じ道路を逆方向に使用するため、同等です)。

実際には3つの可能性があります。

これを 4 つの町に適用すると、(記憶が正しければ) 12 通りの可能性が考えられます。

5 なら 60 です。

6は360になります。

これは階乗と呼ばれる数学演算の関数です。基本的には次のようになります。

5! = 5 × 4 × 3 × 2 × 1 = 120

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

…

25！ = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000

…

50！ = 50 × 49 × … × 2 × 1 = 3.04140932 × 10 ⁶⁴

したがって、巡回セールスマン問題の BigOh はO(n!)または階乗または組み合わせの複雑さです。

町が 200 個に達する頃には、従来のコンピューターで問題を解決するには宇宙に残された時間が足りなくなります。

考えるべきこと。

多項式時間

もう一つ簡単に触れておきたい点は、複雑度がO(n ^a )のアルゴリズムは、多項式複雑度を持つ、または多項式時間で解けると言われているということです。

O(n)、O(n ² ) などはすべて多項式時間です。多項式時間では解決できない問題もあります。このため、世の中には特定のものが使われています。公開鍵暗号は典型的な例です。非常に大きな数の 2 つの素因数を見つけることは計算上困難です。そうでなければ、私たちが使用している公開鍵システムは使用できません。

とにかく、これが BigOh (改訂版) についての私の (できれば平易な英語の) 説明です。

Answer 1

簡単に言うと、私の答えは間違いなく混乱を招くでしょうビッグオー表記(上限) と Big Theta 表記の "Θ" (両側の境界) を組み合わせます。しかし、私の経験では、これは実際には非学術的な環境での議論の典型です。混乱を招いた場合はお詫び申し上げます。

BigOh の複雑さは、次のグラフで視覚化できます。

Big Oh 表記法の最も簡単な定義は次のとおりです。

Big Oh 表記法は、アルゴリズムの複雑さを相対的に表したものです。

この文には、重要かつ意図的に選ばれた単語がいくつかあります。

相対的:同じもの同士しか比較できません。算術乗算を行うアルゴリズムと整数のリストをソートするアルゴリズムを比較することはできません。しかし、算術演算 (1 つは乗算、もう 1 つは加算) を行う 2 つのアルゴリズムを比較すると、意味のあることがわかります。

表現: BigOh (最も単純な形式) は、アルゴリズム間の比較を単一の変数に減らします。その変数は、観察または仮定に基づいて選択されます。たとえば、ソートアルゴリズムは通常、比較操作 (2 つのノードを比較して相対的な順序を決定する) に基づいて比較されます。これは、比較が高価であることを前提としています。しかし、比較は安価でもスワップが高価である場合はどうなるでしょうか。比較が変わります。

複雑さ: 10,000 個の要素をソートするのに 1 秒かかる場合、100 万個の要素をソートするにはどのくらいの時間がかかりますか? この場合の複雑さは、他の何かに対する相対的な尺度です。

残りの部分を読んだら、戻って上記をもう一度読んでください。

BigOh の最も良い例は、算術演算を行うことだと私は考えています。2 つの数字 (123456 と 789012) を考えてみましょう。学校で習った基本的な算術演算は次の通りです。

追加;

減算;

乗算;そして

分割。

これらはそれぞれ操作または問題であり、これらを解決する方法をアルゴリズムと呼びます。

加算は最も簡単です。数字を右に並べて列に数字を加算し、加算の最後の数字を結果に書き込みます。その数字の「十の位」の部分は、次の列に繰り越されます。

これらの数字の加算がこのアルゴリズムで最もコストのかかる操作であると仮定しましょう。当然ながら、これら 2 つの数字を加算するには、6 桁を加算する必要があります (7 桁目を繰り上げる場合もあります)。100 桁の数字 2 つを加算する場合は、100 回の加算が必要です。10,000桁の数字2 つを加算する場合は、10,000 回の加算が必要です。

パターンがわかりますか?複雑さ(つまり演算の数) は、大きい数の桁数nに正比例します。これをO(n)または線形複雑さと呼びます。

減算も同様です (繰り上がりの代わりに借り入れが必要になる場合がある点が異なります)。

掛け算は異なります。数字を並べて、下の数字の最初の桁を取り、それを上の数字の各桁に順番に掛け算し、各桁ごとにこれを繰り返します。したがって、2 つの 6 桁の数字を掛け算するには、36 回の掛け算を行う必要があります。最終結果を得るには、10 回または 11 回もの列の加算を行う必要がある場合もあります。

100 桁の数字が 2 つある場合、10,000 回の乗算と 200 回の加算を行う必要があります。100 万桁の数字が 2 つある場合、1 兆 (10 ¹² ) 回の乗算と 200 万回の加算を行う必要があります。

アルゴリズムは n の 2乗でスケールするため、これはO(n ² )または二次の複雑度になります。ここで、もう 1 つの重要な概念を紹介します。

私たちが気にするのは、複雑さの最も重要な部分だけです。

^{賢明な人は、演算回数を n 2} + 2nと表せることに気付いたかもしれません。しかし、それぞれ 100 万桁の 2 つの数値の例からわかるように、2 番目の項 (2n) は重要ではなくなります (その段階では、演算回数全体の 0.0002% を占めることになります)。

ここでは最悪のシナリオを想定していることに気付くでしょう。6 桁の数字を掛け算する場合、一方が 4 桁でもう一方が 6 桁であれば、掛け算は 24 回だけです。それでも、その「n」の最悪のシナリオ、つまり両方が 6 桁の数字の場合を計算します。したがって、Big Oh 表記はアルゴリズムの最悪のシナリオに関するものです。

電話帳

次に思いつく例は電話帳です。通常はホワイトページなどと呼ばれますが、国によって異なります。ただし、ここでは姓、イニシャルまたは名、場合によっては住所、電話番号の順に人をリストしたものについてお話します。

さて、1,000,000 の名前が載っている電話帳から「John Smith」の電話番号を検索するようにコンピュータに指示するとしたら、どうしますか? S が何番目から始まるか推測できるという事実を無視して (推測できないと仮定しましょう)、どうしますか?

典型的な実装は、真ん中まで開いて、500,000 番目を取り^、それを「スミス」と比較することです。それがたまたま「スミス、ジョン」だった場合、それは本当に幸運でした。それよりずっと可能性が高いのは、「ジョンスミス」がその名前の前か後にあることです。それが後にある場合は、電話帳の最後の半分を半分に分割して繰り返します。それが前にある場合は、電話帳の最初の半分を半分に分割して繰り返します。以下同様に行います。

これはバイナリ検索と呼ばれ、気づいているかどうかにかかわらず、プログラミングで毎日使用されています。

したがって、100 万の名前が載っている電話帳から名前を見つけたい場合、この操作を最大 20 回実行すれば、実際に任意の名前を見つけることができます。検索アルゴリズムを比較する際に、この比較を「n」と決定します。

3 つの名前が記載された電話帳の場合、比較は最大 2 回必要です。

7 の場合は最大 3 かかります。

15の場合は4が必要です。

…

1,000,000 の場合は 20 かかります。

それは驚くほど良いことですよね？

BigOh の用語では、これはO(log n)または対数計算量です。ここで問題となる対数は、ln (底 e)、log ₁₀、log _{2 、またはその他の底である可能性があります。O(2n}² ) と O(100n ² ) がどちらも O(n ² ) であるのと同じように、O(log n) であることは問題ではありません。

ここで、BigOh を使用してアルゴリズムで次の 3 つのケースを判断できることを説明する価値があります。

最良のケース:電話帳検索では、最良のケースは 1 回の比較で名前を見つけることです。これはO(1)または一定の複雑さです。

予想されるケース:上で説明したように、これはO(log n)であり、

最悪の場合:これも O(log n) です。

通常、私たちは最良のケースを気にしません。私たちが関心があるのは、予想される最悪のケースです。場合によっては、これらのいずれかがより重要になることがあります。

電話帳に戻ります。

電話番号を持っていて、名前を見つけたい場合はどうすればよいでしょうか。警察には逆引き電話帳がありますが、そのような検索は一般人には許可されていません。それとも許可されているのでしょうか。技術的には、通常の電話帳で番号を逆引きできます。どのように行うのでしょうか。

まず最初の名前から始めて、番号を比較します。一致すれば素晴らしいですが、一致しなければ次の名前に進みます。電話帳は順序付けされていないため(電話番号順ではない)、このように行う必要があります。

電話番号から名前を検索するには（逆引き）次のようにします。

最良のケース: O(1);

予想されるケース: O(n) (500,000の場合)

最悪の場合: O(n) (1,000,000 の場合)。

巡回セールスマン

これはコンピュータサイエンスでは非常に有名な問題であり、言及する価値があります。この問題では、N 個の町があります。各町は、一定の距離の道路によって 1 つ以上の他の町と接続されています。巡回セールスマン問題は、すべての町を訪問する最短のツアーを見つけることです。

簡単そうに聞こえますか? もう一度考えてみてください。

3 つの町 A、B、C があり、すべての町の間に道路がある場合は、次のようにします。

A → B → C

A → C → B

B → C → A

B → A → C

C → A → B

C → B → A

まあ、実際には、これらのいくつかは同等なので、それより少ないです (たとえば、A → B → C と C → B → A は同じ道路を逆方向に使用するため、同等です)。

実際には3つの可能性があります。

これを 4 つの町に適用すると、(記憶が正しければ) 12 通りの可能性が考えられます。

5 なら 60 です。

6は360になります。

これは階乗と呼ばれる数学演算の関数です。基本的には次のようになります。

5! = 5 × 4 × 3 × 2 × 1 = 120

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

…

25！ = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000

…

50！ = 50 × 49 × … × 2 × 1 = 3.04140932 × 10 ⁶⁴

したがって、巡回セールスマン問題の BigOh はO(n!)または階乗または組み合わせの複雑さです。

町が 200 個に達する頃には、従来のコンピューターで問題を解決するには宇宙に残された時間が足りなくなります。

考えるべきこと。

多項式時間

もう一つ簡単に触れておきたい点は、複雑度がO(n ^a )のアルゴリズムは、多項式複雑度を持つ、または多項式時間で解けると言われているということです。

O(n)、O(n ² ) などはすべて多項式時間です。多項式時間では解決できない問題もあります。このため、世の中には特定のものが使われています。公開鍵暗号は典型的な例です。非常に大きな数の 2 つの素因数を見つけることは計算上困難です。そうでなければ、私たちが使用している公開鍵システムは使用できません。

とにかく、これが BigOh (改訂版) についての私の (できれば平易な英語の) 説明です。

「Big O」表記法のわかりやすい英語の説明は何ですか? 質問する

ベストアンサー1

電話帳

巡回セールスマン

多項式時間

おすすめ記事