問題タブ [amortized-analysis]

整数が 2 の累乗ではなく、フィボナッチ数の和として表されると仮定すると、 を100101表しますF(6)+F(3)+F(1)=8+2+1=11( と仮定しF(1)=F(2)=1ます)。O(1) 償却時間で、この表現の下で整数をインクリメントしたいと考えています。

インクリメントのアルゴリズムがあります。直感的には、1 のビットが 2 つ連続してはならないということです。したがって、最初に最下位の 0 ビットを 1 に設定し、次に最上位ビットから始めて、数値に 2 つの連続する 1 ビット、たとえばビット i と i-1 がある場合は、両方を 0 に設定し、i+1 を設定します。 2 つの連続する 1 ビットがなくなるまで、これを再帰的に行います。

私は会計法を使用して償却分析を行います。したがって、インクリメント操作ごとに k ドルを付与し、ビット フリップごとに 1 ドルの費用がかかります。ただし、k の正しい値を設定して証明するのに問題があります。経験的にはうまくいくと思いますk=3が、それを証明する方法がわかりません。

O(n)/n=1 は、レッスン 5 のデータ構造に関するコースラ コースの償却分析: 集計方法で指定されている償却分析の集計方法ではどのようになっていますか?

配列を使用してヒープを実装し、配列がいっぱいになるたびに、それを 2 倍のサイズの配列にコピーするとします。要素をヒープに挿入する際の償却時間の複雑さ (最悪の場合) はどれくらいですか?

T(n) = n * n(最悪の場合、n 回の操作のシーケンスの総コストの上限) があると思います。1 つの式によると、償却された複雑さはT(n) / n = n^n / n = nです。

しかし、私が得るlog(n)か下げるかは直感的に非常に明確なので、それは非常に間違っていると思います... では、これをどのように計算すればよいでしょうか?

すべての操作分析のフィボナッチ ヒープでは、本質的に償却されます。二項ヒープの場合のように、通常の分析ができないのはなぜですか。

Data.Listモジュールでは、次のデータ構造が使用されます。

スニペットの言及の上のコメントは次のようになります。

キューは (償却された) O(1)snocと O(1 ) を保証します。つまり、リストのような構造への O(1) 変換は、通常のリストよりも一定の係数だけ遅いunconsと考えることができます。つまり、O(n toListSB) コストは、リストを消費するにつれて段階的に増加します。

toListSBO(1) での作業が償却される理由がわかりません。右側のリストの長さは、連続する 2 のべき乗の間でどんどん大きくなっていきませんか?

ウィキペディアによると、二項ヒープでの挿入操作の償却時間は O(1) です。単一の挿入操作の場合、時間の複雑さは O(log n) です。しかし、その償却時間はどのようにして O(1) になるのでしょうか?

私は決勝戦を検討していますが、次の問題に遭遇しました:

バイナリ ヒープには、デフォルトで優先キュー セマンティクスがあります。要素を n 回挿入すると、「消える」前に n 回削除する必要があります。代わりにセマンティクスが設定されたバイナリ ヒープを実装するとします。この場合、挿入操作と削除操作はどれくらい速くなりますか?

(a) 挿入: O(n) 削除: O(logn)

(b) 挿入: O(log n) 削除: O(n)

(c) 挿入: O(log n) 削除: O(log n)

(d) 挿入: O(1) 削除: O(n2)

(e) 上記のいずれでもない。

優先キュー セマンティクスで実装されたヒープに挿入するには、O(logn) になり、削除も同様です。ただし、セットの場合、挿入と削除はセット自体の多くの要因に依存します。答えはどうあるべきだと思いますか。