79

誰かが償却された複雑さを素人の言葉で説明できますか? 私はオンラインで正確な定義を見つけるのに苦労しており、それがアルゴリズムの分析とどのように関連しているのかわかりません. 外部から参照されたものであっても、役に立つものは何でも高く評価されます。

4

6 に答える 6

101

償却された複雑さは、一連の操作にわたって評価された、操作ごとの総費用です。

アイデアは、シーケンス全体の総費用を保証する一方で、個々の操作が償却原価よりもはるかに高くなることを許可することです。

例：
C++の動作std::vector<>。push_back()ベクトルサイズを事前に割り当てられた値より大きくすると、割り当てられた長さが2倍になります。

そのため、シングルの実行には時間push_back()がかかる場合がありますO(N)（配列の内容が新しいメモリ割り当てにコピーされるため）。

ただし、割り当てのサイズが2倍になったため、への次のN-1呼び出しpush_back()はそれぞれO(1)実行に時間がかかります。したがって、N操作の合計にはまだ時間がかかりO(N)ます。これにより、1回の操作あたりpush_back()の償却原価が得られます。O(1)

特に明記されていない限り、償却された複雑さは、操作のシーケンスに対する漸近的な最悪の場合の保証です。これの意味は：

  • 償却されていない複雑さの場合と同様に、償却された複雑さに使用されるbig-O表記は、固定の初期オーバーヘッドと一定のパフォーマンス要因の両方を無視します。したがって、big-Oの償却パフォーマンスを評価するために、一般に、償却された操作のシーケンスは、固定の初期費用を償却するのに「十分な長さ」であると想定できます。具体的にはstd::vector<>、この例では、これが、実際に追加の操作が発生するかどうかを心配する必要がない理由ですN。分析の漸近的な性質は、すでに発生することを前提としています。

  • 任意の長さに加えて、償却分析では、コストを測定している操作のシーケンスについての仮定は行われません。これは、考えられる操作のシーケンスに対する最悪の場合の保証です。操作がどれほどひどく選択されたとしても（たとえば、悪意のある敵によって！）、償却分析では、十分に長い一連の操作のコストが、償却コストの合計よりも一貫して高くならないことを保証する必要があります。これが、（修飾子として特に言及されていない限り）「確率」と「平均ケース」が償却分析に関連しない理由です。通常の最悪の場合のbig-O分析よりも重要です。

于 2013-02-26T01:18:43.543 に答える
33

償却分析では、一連のデータ構造操作を実行するために必要な時間は、実行されるすべての操作にわたって平均化されます...償却分析は、確率が含まれないという点で平均ケース分析とは異なります。償却分析は、最悪の場合の各操作の平均パフォーマンスを保証します。

（Cormen et al。、 "Introduction to Algorithms"から）

これは、時間が平均化されていることと、平均的なケースの分析ではないことの両方を示しているため、少し混乱する可能性があります。それでは、これを財務的な例えで説明してみましょう（実際、「償却済み」は、銀行と会計に最も一般的に関連付けられている単語です）。

宝くじを運営しているとします。（すぐに入手できる宝くじを購入するのではなく、宝くじ自体を操作します。）10万枚のチケットを印刷し、それぞれ1通貨単位で販売します。それらのチケットの1つは、購入者に40,000通貨単位の資格を与えます。

これで、すべてのチケットを販売できると仮定すると、60,000通貨単位を獲得できます。つまり、売上高100,000通貨単位から、40,000通貨単位の賞金を差し引いたものです。あなたにとって、各チケットの価値は0.60通貨単位であり、すべてのチケットにわたって償却されます。これは信頼できる値です。あなたはそれに頼ることができます。自分でチケットを売るのに飽きて、誰かがやって来て、それぞれ0.30通貨単位でチケットを売ろうと申し出た場合、あなたは自分がどこに立っているかを正確に知っています。

宝くじの購入者にとっては、状況は異なります。宝くじを購入すると、購入者は0.60通貨単位の損失を予想します。しかし、それは確率論的です。購入者は、30年間、毎日10枚の宝くじ（10万枚強）を購入する可能性があります。または、ある日自発的に1つのチケットを購入し、39,999通貨単位を獲得する場合もあります。

データ構造分析に適用すると、最初のケースについて話します。このケースでは、その種のすべての操作に対して、データ構造操作（挿入など）のコストを償却します。平均ケース分析では、確率的操作（検索など）の期待値を扱います。この場合、すべての操作の合計コストを計算することはできませんが、単一の操作の期待コストの確率的分析を提供できます。

償却分析は、高コストの操作がまれな状況に適用されるとよく​​言われますが、それはよくあることです。しかしいつもではない。たとえば、2つのスタックで構成される先入れ先出し（FIFO）キューである、いわゆる「バンカーズキュー」について考えてみます。（これは古典的な機能データ構造です。不変の単一リンクノードから安価なLIFOスタックを構築できますが、安価なFIFOはそれほど明白ではありません）。操作は次のように実装されます。

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

ここで、空のキューで開始および終了すると仮定すると、putとの償却コストはであると主張しgetます。O(1)分析は簡単です。私は常にput右側のスタックに移動getし、左側のスタックから移動します。Ifしたがって、句を除いて、それぞれputはでありpush、それぞれgetはでありpop、どちらもO(1)。です。If句を何回実行するかはわかりませんが（ putsとgetsのパターンによって異なります）、すべての要素が右側のスタックから左側のスタックに1回だけ移動することはわかっています。したがって、nsとnsのシーケンス全体の総コストは次putのようになりgetますpush。nes、n pops、およびn moves、ここでamoveはpopの後に：が続きます。つまり、push2n演算（ nsおよびns ）は、2nesおよび2nsになります。したがって、単一または1の償却原価です。putgetpushpopputgetpushpop

銀行家のキューは、償却された複雑さの分析（および「償却された」という単語と財務との関連付け）のために正確に呼び出されることに注意してください。バンカーのキューは、以前はよくあるインタビューの質問に対する答えですが、今ではあまりにもよく知られていると思います。償却されたO（1）時間で次の3つの操作を実装するキューを考え出します。

1）キューの最も古い要素を取得して削除します。

2）新しい要素をキューに入れます。

3）現在の最大要素の値を見つけます。

于 2013-02-26T01:28:25.343 に答える
23

「償却された複雑さ」の原則は、何かを実行すると非常に複雑になる場合がありますが、それほど頻繁に実行されるわけではないため、「複雑ではない」と見なされるということです。たとえば、ときどきバランス調整が必要なバイナリ ツリーを作成する場合2^n(挿入ごとに 1 回など)、ツリーのバランス調整は非常に複雑ですが、n 回の挿入ごとに 1 回しか発生しないためです (たとえば、挿入番号 256 で 1 回、次に挿入番号 256 で 1 回)。 512th、1024thなど)。他のすべての挿入では、複雑さは O(1) です - はい、n 回の挿入ごとに 1 回 O(n) かかりますが、これは1/n確率にすぎません - したがって、O(n) に 1/n を掛けて O(1) を取得します。これは、「O(1) の償却された複雑さ」と言われています。要素を追加すると、ツリーの再調整にかかる時間が最小限になるためです。

于 2013-02-26T00:45:48.650 に答える
6

償却とは、繰り返しの実行で分割されることを意味します。最悪の場合の動作が頻繁に発生しないことが保証されています。たとえば、最も遅いケースが O(N) であるが、それが発生する可能性が O(1/N) であり、それ以外の場合にプロセスが O(1) である場合、アルゴリズムは定数 O(1) 時間を償却します。 . 各 O(N) 回の実行の作業が、他の N 回の実行に分割されると考えてください。

コンセプトは、合計時間を分割するのに十分な実行数に依存します。アルゴリズムが 1 回しか実行されない場合、または実行するたびに期限を守らなければならない場合は、最悪の場合の複雑さがより重要になります。

于 2013-02-26T00:47:07.690 に答える
4

ソートされていない配列の k 番目に小さい要素を見つけようとしているとします。配列のソートは O(n logn) になります。したがって、k 番目に小さい数を見つけることは、単にインデックスを見つけることなので、O(1) になります。

配列は既にソートされているため、再度ソートする必要はありません。最悪のシナリオに何度も遭遇することはありません。

k 番目に小さいものを見つけようとして n 個のクエリを実行しても、O(1) よりも優位であるため、O(n logn) になります。各操作の時間を平均すると、次のようになります。

(n logn)/n または O(logn)。したがって、時間の複雑さ/操作の数。

これは償却された複雑さです。

私はそれがどうなるかだと思います、私もそれを学んでいます..

于 2014-06-21T07:26:53.727 に答える
2

これは、アルゴリズム内のさまざまな分岐の最悪の場合の複雑さと、その分岐を実行する確率を乗算し、結果を加算することにいくらか似ています。そのため、分岐が行われる可能性が非常に低い場合、複雑さへの影響は少なくなります。

于 2013-02-26T00:47:10.670 に答える