問題タブ [amortized-analysis]

インクリメント バイナリ カウンタとデクリメント バイナリ カウンタの償却コストは同じですか? つまり、n のインクリメントまたはデクリメントに対して O(n) ですか? また、潜在的な方法を使用してバイナリ減分カウンターの償却コストを計算する方法を誰かが説明できますか?

そのため、要素が追加されるたびに動的配列のサイズが 2 倍になると、要素が O(n) n であることを拡張するための時間の複雑さがわかりました。配列がコピーされ、いっぱいになったときにサイズが 1 だけ大きい新しい配列に移動された場合はどうなるでしょうか。(2 倍にする代わりに) 定数 C でサイズを変更すると、時間の計算量は常に O(n) になりますか?

この問題に出くわしたとき、私は最終試験の勉強をしていました。
1aの場合、償却された複雑さはO(1)だと思います.x mod Nは十分にまばらで、失敗した場合の線形プローブを行うためです.ただし、それを正確に述べたり証明したりする方法はわかりません.

1bの場合、同じ場所にハッシュされるため、挿入するたびに線形的にプローブされますが、そこからランタイムを導出する方法もわかりません。

動的配列の償却分析で間違った総コストを計算するために、宿題にポイントをドッキングしました。採点者はおそらく合計のみを見て、私が行った手順は見ていないと思います.mallocを説明したと思いますが、回答キーは考慮していませんでした.

ここに私の分析のセクションがあります：

表示された例では malloc が説明されていませんでしたが、ビデオを見て非常に理にかなっていたので、そこに入れました。malloc は比較的コストのかかる操作ですが、ここではおそらく O(1) になるので、省略できたはずです。

しかし、私の質問は次のとおりです。この種の分析を行う場合、コストを計算する方法は 1 つしかありませんか? 客観的な善悪のコストはありますか、それとも本当に重要なことは結論です。

howmework に次の質問があります。

3 つのスタックを使用して Deque を実装します。Deque には、InsertHead、InsertTail、DeleteHead、DeleteTail という操作があります。各操作の償却時間が O(1) であることを証明します。

私が試みたのは、問題をハノイ問題として見ることです。スタックを次のように呼び出しましょう: L(左)、M (中央)、R(右)。

擬似コードの実装:

InsertTail と DeleteTail は、上記の実装と同じ原則に基づいています。償却された時間が O(1) であることをどのように証明できますか? L には N 個の要素が存在する可能性があり、wile ループは O(n) かかるため、deleteHead を N 回呼び出して償却時間を計算すると、複雑さは O(n^2) になりませんか?

上記の実装が償却時間でO(1)かかることを証明するにはどうすればよいですか?

ランダム化問題で困っています。:)

ランダム化されたアルゴリズムである A は、入力 x が素数であるかどうかを判断します。

このアルゴリズムは次のように機能します。

1- x が素数の場合、A は YES を出力します

2- x が素数でない場合、A は確率 3/4 で NO を出力します。

アルゴリズム A が少なくとも 1-(1/k) の確率で NO を出力するようにしたい場合、少なくとも何回 A を実行する必要がありますか?

注: 1 つの NO の答えは、与えられた入力 x が素数でないことを意味します。

何か案が？