問題タブ [amortized-analysis]

フィボナッチ ヒープを理解するのは難しいことがわかっています。しかし、いくつかの質問は私には本当に不明確です:

• t + 2m のような潜在的な関数を選択するのはなぜですか? 理由は何ですか？
• ノードのマーキングの背後にある理由は何ですか?ノードをルート リストなどに配置すると便利だと思いますが、なぜそのようなスキームを考え出すのでしょうか?

ありがとう！

タイトルをうまく説明できませんでした。申し訳ありません。

すべてのデータ構造について、特定の償却された実行時間でいくつかの操作をサポートし、最悪の場合、同じ実行時間で同じ操作をサポートする別のデータ構造があるということですか? 反復的で一時的なデータ構造と関数型のデータ構造の両方に興味があります。

私は、この質問が以前に尋ねられたにちがいないと確信しています。正しい検索キーワードが見つからないようです (Google、SO、TCS で)。{yes, no, open} で引用された回答を探しています。

整数の配列 (例: 123、132、213、231、312、323) の次の辞書順列を計算するアルゴリズムを作成しました。コードは必要ないと思いますが、以下に含めました。

O(n) の最悪の場合の時間コストを適切に決定したと思います。ここで、n は配列内の要素の数です。ただし、「償却コスト」を使用すると、平均的なケースで時間コストが O(1) として正確に表示されることがわかります。

質問：

これを O(1) として表示する「会計方法」を学びたいのですが、各操作にコストを適用する方法がわかりません。会計方法:リンク: Accounting_Method_Explained

考え:

ポジションの値を変更するコストを適用するか、そのコストをスワップに適用することを考えました。しかし、それは本当にあまり意味がありません。

} // getNext を終了します

バイクは風があれば時速 24 キロで走行できますが、逆風では時速 12 キロしか走れません。バイカーが同じポイントでスタートし、フィニッシュすると仮定します。

乗客の償却旅行率はいくらですか?

どのように答えにたどり着いたのかわかりません。講義ノートを読みましたが、少し混乱しています。

ありがとう

漸近解析とどう違うのですか？いつ使用しますか、またその理由は何ですか。

私はこれらのようにうまく書かれているように見えるいくつかの記事を読みました：

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

しかし、私はまだこれらの概念を完全には理解していません。

それで、誰かが私のためにそれを単純化してくれますか？

私は、それぞれがO(1)の償却された複雑さで実行されるn個の連続した操作のセットを持っています。セット全体が O(n) の最悪の場合の時間の複雑さで実行されていると言えますか? どうやって証明するの？

Java HashMapのkeySetの償却分析が何であるか知っている人はいますか? O(1)?

それらを繰り返していますO(n)か？

このような構造は、リアルタイムアプリケーション（ユーザーインターフェイスなど）に必要です。（ユーザーは、ボタンのクリックに0.1秒または0.2秒かかるかどうかは気にしませんが、100回目のクリックで卓越した遅延計算が強制され、続行するのに10秒かかるかどうかは気になります。）

私は岡崎の論文「純粋関数型データ構造」を読んでいました。彼は、償却された境界を持つ怠惰なデータ構造を、すべての操作で同じ最悪の場合の境界を持つ構造に変換するための興味深い一般的な方法について説明しています。アイデアは、各更新で未評価のサンクの一部が強制されるように計算を分散することです。

Haskellに標準コレクション（、、など）のそのような実装はありますMapか？Set

コンテナパッケージには

各操作の宣言されたコストは、最悪の場合または償却されますが、構造が共有されている場合でも有効です。

したがって、単一の操作の最悪の場合の範囲は保証されません。のような厳密なバリアントがありますがData.Map.Strict、キーと値は厳密です。

キーと値の引数はWHNFに対して評価されます。キーと値は、マップに保存される前にWHNFに評価されます。

その構造の（可能な）厳密さについては何もありません。

操作コストが正確に 2 のべき乗であり、それ以外の場合は 1 であるnデータ構造に対する一連の操作で、操作ごとの償却コストを見つけようとしています。ithii

コストの合計を数値まで表現する方法を見つける必要があると思いますが、n行き詰まっています。i特別な、より高価な値が父と離れて発生していることがわかります。

i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...

つまり、2 の 1 乗と 2 乗の間に数がないように見えます。次に 1 の数、次に 3、次に 7 です。これをしばらく見てみると (間違っていたら訂正してください)、jthと2 の累乗の間の 2 の非累乗kthは です2^(j-1) - 1。

しかし、どうすればこれをすべてまとめて合計することができますか? 2 の実際のべき乗の数自体を組み合わせたものを少し見ることができますがjs、すべてを 1 つの概念にまとめるのに苦労しています。

すべてのビットをゼロにインクリメントおよびリセットするという 2 つの操作をサポートするバイナリ カウンターがあるとします。単一ビットの変更または検査に Theta(1) 時間かかる場合、カウンターをビット配列として実装して、最初はゼロのカウンターでの一連のインクリメントおよびリセット操作に O(n) 時間かかるようにするにはどうすればよいでしょうか?

集計分析により、すべてのビットが毎回反転する必要はないという事実を考慮すると、インクリメントのみを許可するカウンターでは、n 回の操作に O(n) の時間がかかることがわかりました。しかし、インクリメント リセット カウンターの実装方法に行き詰まっています。私の知る限り、フリップはフリップであり、1111 が魔法のように通常より速く 0000 になることはありません。ただし、インクリメント操作を使用すると、非常に高価なすべて 1 の状況が頻繁に発生することはありません。

本当の問題は、リセットユーティリティで効率的なカウンターを実現する戦略が実際にあるのか、それともインクリメント操作だけでカウンターのようになることを証明しようとしているだけなのかということです。私が持っている唯一のヒントは、「上位1へのポインターを保持する」ことです。これは、前者を示唆しているようです。