4

私は仕事に応募してきましたが、アルゴリズムの時間/空間の複雑さについての質問を聞くたびに、うんざりしてつまずきます. どれだけ読んでも、私の脳はそれを理解しないようにプログラムされているようで、その理由は、学校をスキップして数学のバックグラウンドが非常に低いという事実にあると思います. これは通常のSOの質問ではない可能性があり、基本的に数学に関するものであるために削除される可能性さえありますが、少なくとも、この質問で次にどこに行くべきかを理解したいと思っています.

4

3 に答える 3

8

職場の人がなぜそこに入るのかわからないので、ここにいくつかの例を示します。全体の「複雑さ」は、アルゴリズムが使用する時間 (またはメモリ) の指標を提供することです。

ここで、値を持つ配列がある場合、特定のインデックスで値にアクセスするのは O(1) -- 定数です。配列内の要素の数は関係ありません。インデックスがあれば、要素を直接取得できます。

一方、特定の値を探している場合は、すべての要素を調べる以外に選択肢はありません (少なくともその要素が見つかるまでは、複雑さの問題ではありません)。したがって、ランダムな配列での検索は O(n) です。実行時間は要素の数に対応します。

一方、並べ替えられた配列がある場合は、「バイナリ検索」を実行できます。これは O(log n) になります。"Log n" は 2 の対数で、基本的に 2^n の逆数です。たとえば、2^10 は 2*2*2*2...*2 10 回 = 1024 であり、log2(1024) は 10 です。したがって、O(log n) を使用するアルゴリズムは一般的にかなり優れていると見なされます。二分探索を使用してソートされた配列内の要素を検索します。配列に最大 1024 個の要素がある場合、二分探索ではそのうちの 10 個を調べるだけで値を見つけることができます。1025 ～ 2048 要素の場合は最大 11 ピーク、2049 ～ 4096 要素の場合は 12 などです。したがって、要素を追加しても、実行時間はゆっくりと増加します。

もちろん、事態はさらに悪化する可能性があります。単純な並べ替えアルゴリズムは O(n**2) になる傾向があります。つまり、要素が 2 つしかない配列の場合は 2^2 = 4 回の「操作」が必要であり、配列に 3 つの要素がある場合は 3^2 = 9 回、配列に 4 つの要素がある場合は 16 など。要素が 1000 個しかない配列では、並べ替えに 1000*1000 = 100 万回の比較が必要になることを考えると、実際にはかなり悪いことです。これは指数関数的成長と呼ばれ、もちろんさらに悪化する可能性があります: O(n^3)、O(n^4) など。

「良い」並べ替えアルゴリズムは O(n*log n) です。1024 個の要素を持つ配列を想定すると、これは 1024*10=10240 になります --- 以前の 100 万個よりもはるかに優れています。

これらの O(...) を実行時の動作 (またはメモリに適用する場合はメモリ フットプリント) の指標として使用するだけです。数値がどのように変化するかを確認できるように実数を挿入しましたが、それらは重要ではなく、通常、これらの複雑さは最悪のケースです。それにもかかわらず、数字を見るだけで、「一定時間」が明らかに最良であり、ランタイム（またはメモリ使用）が非常に高速になるため、指数関数は常に悪いです。

EDIT：また、定数要因にはあまり興味がありません。通常、「O(2n)」は表示されません。これは「O(n)」のままです。実行時間は要素の数に直接関係します。

于 2012-08-19T13:56:18.257 に答える
7

アルゴリズムの時間/空間の複雑さを分析するには、高校の知識が必要です。私はこれを大学で学びました。私の最初の学期の間、私は元気でした。

基礎の関心分野は次のとおりです。

上記は、アルゴリズムの複雑さを分析する場合に当てはまります。問題の複雑さを計算することは、まだ研究中の非常に深い分野です -複雑さの理論。これには、集合論、計算理論、高度な微積分、線形代数などに関する幅広い知識が必要です。

于 2012-08-19T13:46:12.307 に答える
5

微積分、総和級数、離散数学についてある程度知っていることはすべて良いことですが、あなたの質問と業界での私の限られた経験からすると、面接担当者がそのレベルの理解を期待しているとは思えません。

実際には、多くの数学的思考をしなくても、時間と空間の複雑さについて有用な大きなステートメントを作成できます。時間の複雑さの観点から説明する基本は、言語の抽象度を下げるだけです。

ビッグ O 時間複雑度は、アルゴリズムの最悪の場合の実行時間が入力のサイズにどのように対応するかを示します。big-O 関数から得られる実際の数値は、特定のサイズの入力に対してアルゴリズムが実行する定数時間演算の数を示しています。

したがって、big-O 関数は、アルゴリズムが実行する定数時間操作の数を単純にカウントします。

  • 一定時間の操作は O(1) と呼ばれます。[シーケンスにも一定の時間がかかるため、一定時間操作の固定長シーケンスも O(1) であることに注意してください。]

O(k) = O(1)、任意の定数 k に対して。

  • アルゴリズムが複数の操作を連続して実行する場合、それらのコストを合計します。

O(f) + O(g) = O(f + g)

  • アルゴリズムが操作を複数回実行する場合、操作のコストに実行回数を掛けます。

n * O(f) = O(n * f)

O(f) * O(f) * ... * O(f) = O(f^n)、左辺に n 個の項があります

  • 古典的な big-O 関数は log(n) で、これは常に「n 個のアイテムを含むバランスの取れたツリーの高さ」に対応します。並べ替えが O(n log(n)) であることを知っているだけで済みます。

  • 最後に、入力のサイズが大きくなるにつれて、これが他のすべての項を支配するため、big-O 関数で最も急速に増加する項のみを報告します。結果のスケーリング プロパティのみに関心があるため、定数係数も破棄されます。

たとえば、O(2(n^2) + n) = O(n^2)。

2 つの例を次に示します。

nアイテムのバブルソート

アイテムを走査するたびに、(少なくとも) 1 つのアイテムが所定の位置に並べ替えられます。したがって、すべてのアイテムをソートするには n 回のトラバーサルが必要です。

O(bubble-sort(n)) = n * O(traversal(n))
                  = O(n * traversal(n))

項目の各走査には、n - 1 回の隣接する比較と交換操作が含まれます。

O(traversal(n)) = (n - 1) * O(compare-and-swap)
                = O((n - 1) * O(compare-and-swap))

コンペア アンド スワップは一定時間の操作です。

O(compare-and-swap) = O(1)

条件をまとめると、次のようになります。

O(bubble-sort(n)) = O(n * (n - 1) * 1)
                  = O(n^2 - n)
                  = O(n^2)

n 個のアイテムのマージソート

マージソートは、リストがソートされるまで、アイテムをペアにマージし、ペアを 4 に、4 を 8 にマージするというように、ボトムアップで機能します。このような一連の操作をそれぞれ「マージ トラバーサル」と呼びます。n = 2 ^ log_2(n) であるため、最大で log_2(n) 回のマージ トラバーサルが可能であり、各レベルでマージされるサブリストのサイズを 2 倍にしています。したがって、

O(merge-sort(n)) = log_2(n) * O(merge-traversal(n))
                 = O(log_2(n) * merge-traversal(n))

各マージ トラバーサルは、すべての入力データを 1 回トラバースします。各入力項目は、少なくとも 1 つの比較および選択操作の対象であり、各比較および選択操作は、「発行」する項目のペアの 1 つを選択します。したがって

O(merge-traversal(n)) = n * O(compare-and-select)
                      = O(n * compare-and-select)

それぞれの比較と選択の操作には一定の時間がかかります。

O(compare-and-select) = O(1)

用語を集めると、

O(merge-sort(n)) = O(log_2(n) * n * 1)
                 = O(n * log_2(n))
                 = O(n * log(n)), since change of log base is 
                                  multiplication by a constant.

たぁぁぁぁ！

于 2012-08-20T01:02:05.703 に答える