問題タブ [amortized-analysis]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
data-structures - バイナリ ヒープの償却分析
したがって、通常のバイナリ ヒープには、O(log(n)) 最悪の時間である操作 extract_min があります。extract_min の償却コストが O(1) であるとします。n をヒープのサイズとする
したがって、n 回の extract_min 操作が実行され、最初に n 個の要素が含まれていたシーケンスです。これは、各操作が O(1) であるため、シーケンス全体が O(n) 時間で処理されることを意味しますか?
java - ArrayList 基礎となる配列コスト
私は最近、Java から ArrayList を読んでいました。私の理解では、ArrayList がその容量に達すると、サイズ変更メソッドが呼び出され、元のサイズの2 倍の新しい基になる配列が作成されます。この場合、挿入は O(n) と見なすことができますが、平均的には O(1) のままです。ただし、具体的に2倍のサイズに増加した理由については混乱しています。元の容量の3倍に増やしたほうがいいでしょうか？