問題タブ [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.
algorithm - 最小ヒープの償却分析?
空の最小ヒープ上でn
任意の挿入および削除操作を行う場合 (最小ヒープ内の指定された削除場所で)。挿入O(1)
と削除の償却分析はなぜO(log n)
ですか?
誰でも私のためにそれを明確にすることができますか?
algorithm - ヒープの償却分析
このトピックにたどり着いたとき。
5-1 ページの下部にあるこの本の中で、 Binomial Queues、Fibonacci Heap、およびSkew Heapの挿入操作の償却コストは O(1)であり、削除操作の償却コストは O(log n)であると読みました。次に著者は、ペアリング ヒープの挿入操作の償却コストは O(1) であり、削除操作の償却コストは O(log n) であると書いています。
この宿題では、ヒープのタイプを定義せずに、このリンクの 3 番目 (3) の割り当てと解決策 が挿入用に O(log n) を、削除用に O(1) を書きました。
この宿題で別の著者は、二項ヒープには挿入操作の O(log n) と削除操作の償却コスト O(1) があると述べています。
問題は、どちらが正しいかです。私はかなり混乱しています。
java - 配列がいっぱいになったときに配列のメモリを再割り当てすると、拡張可能配列は何をしますか?
動的に割り当てられた配列がある場合、挿入を行うには O(1) が必要であるというこの質問に遭遇しました。しかし、配列がいっぱいになると、配列にダブルスペースを再割り当てする必要があるため、古い配列のコピーには O(n) かかります。
O(1)にする方法はありますか?
拡張可能な配列について述べている記事をいくつか読みましたが、それを静かに理解していません。誰かがそれをもっと説明するのを助けることができますか?
どうもありがとう。
algorithm - 償却複雑度
私のアルゴリズムのクラスでは、償却された複雑性について説明しました。残念ながら体育大会で不在のため参加できませんでした。教授に連絡してこれを説明しようとして失敗した後、ここで質問することになりました。Amortized Complexity とは何ですか? どうすれば見つけられますか? やるべき仕事を任されたが、どうしたらいいのかわからない。非常に役立つか、他の説明への参照を提供する1つの質問で私を助けることができれば.
問題は次のとおりです。
次のアルゴリズムを検討し、オーバーフローがないと仮定して、n ビットの配列として表される 2 進数に 1 を加算します。
このアルゴリズムは、最悪の場合、明らかに O(n) です。その償却複雑度が O(1) であることを示します。
最悪のケースが O(n) である理由はわかりますが、償却後の複雑さが O(1) である理由はわかりません。または、そのことについては、償却された複雑さでさえあります。
algorithm - 償却分析とコンテスト 質問、問題はありますか?
次のようなローカル コンテストの質問に出くわしました。
空の場合、任意の操作MIN-Heap
を実行します (最小ヒープ内の削除の場所を指定して)。とは何ですか?n
insert
delete
amortized analysis
insert
delete
I) O(log n) を挿入、O(1) を削除
II) O(log n) を挿入、O(log n) を削除
III) O(1) を挿入、O(1) を削除
IV) O(1) を挿入、O(log n) を削除
ヒープのタイプが定義されていないため、これはこの質問の問題だと思います。いくつかのヒープにはオプション (1) と (4) があることを Google で読みました。専門家の観点から、この質問で言うことができますcan we select all options as True?
amortized-analysis - ループの時間計算量分析:
時間計算量が O(nlogn) ではなく O(n) なのはなぜですか? 外側のループの複雑さと内側のループの複雑さを掛け合わせる必要はありませんか?
sorting - ヒープソート時間の複雑さの深い理解
大学でデータ構造コースを勉強したとき、次の公理を学びました。
ヒープへの新しい数値の挿入には、最悪の場合O(logn)かかります (リーフとして挿入されたときにツリー内のどのくらいの高さに到達するかによって異なります)。
空のヒープから開始して n 個の挿入を使用してnノードのヒープを構築すると、償却分析を使用してO(n)時間に合計されます
最小値の削除には、最悪の場合O(logn)時間がかかります (最後のリーフと交換された後、新しい最上位ノードがどれだけ低くなるかによって異なります)。
ヒープが空になるまで、すべての最小値を 1 つずつ削除するには、O(nlogn)時間の複雑さがかかります
注意:「ヒープソート」アルゴリズムの手順は次のとおりです。
- すべての配列値をヒープに追加します: amortized-analysis トリックを使用してO(n)時間の複雑さに合計します
- ヒープから最小値をn回ポップし、i番目の値を配列のi番目のインデックスに配置します。最小値をポップするときに償却分析トリックが機能しないため、O(nlogn) 時間の複雑さ
私の質問は:ヒープを空にするときに償却分析トリックが機能せず、ヒープソートアルゴリズムがO(nlogn)時間ではなくO (nlogn) 時間かかるのはなぜですか?
編集/回答
ヒープが配列に格納されている場合 (ポインターを持つ動的ツリー ノードではなく)、ヒープをボトムアップで構築できます。つまり、リーフからルートまで開始し、償却分析を使用して合計時間の複雑さを取得できます。O(n)の、ヒープの最小値のボトムアップを空にすることはできません。
objective-c - ローンの償却返済日の計算方法
ローンの償却を数えたいのですが、返済日の計算方法がわかりません。
私は、、、を持っLoan amount
てInterest rate
いMonthly paymnet
ますLoan Start date
。これらの 4 つの値から、iOS でのローン返済日を知りたいです。
Interest
のMonthly Amount
ように数えます
誰でも私を助けることができますか?