プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

メルドオペレーションの償却原価

溶融操作の償却原価を計算することは困難な作業です。主な難しさは、ランダムな一連の操作のさまざまなポイントで実行される操作のコストの幅広い変動を累積することです。私たちの設計目標は一連の操作のコストに影響されますが、一連の操作のコストの観点から操作の償却コストの概念を定義することは何も導きません。実際のコストの変動を設定するための潜在的な関数を実装することは、状況を処理するための完璧な方法です。次のトピックでは、償却コストの概念について説明します。

Bを基本演算P={P 1 の抽象データ型（ADT）とします。 、P 2 、……、P k }そしてDSをBを実装するデータ構造とします。Fを非負実数へのデータ構造の構成で指定された潜在的な関数とします。さらに、F（Φ）=0とします。DS j とします。 構成DSで操作Pkを実行した場合に取得する構成を指定し、CがDSでPkを実行する実際のコストを示すようにします。

次に、DSで動作するPkの償却コストはa（Pk、DS）で表され、

で与えられます。

a（P k 、DS）=C + F（DS j ）– F（DS）

a（P k 、DS）≤cjg（m）、サイズmのすべての構成DSの場合、Pkの償却原価はO（g（m））であると結論付けます。


  1. クラスカル（最小スパニングツリー）MSTアルゴリズム

    連結グラフG（V、E）があり、すべてのエッジの重みまたはコストが示されています。クラスカルのアルゴリズムは、グラフとコストを使用して最小全域木を見つけます。 マージツリーアプローチです。最初はさまざまなツリーがありますが、このアルゴリズムは、コストが最小のエッジを取得することでそれらをマージし、単一のツリーを形成します。 この問題では、すべてのエッジが一覧表示され、コストに基づいて並べ替えられます。リストから、最小コストのエッジが取り出されてツリーに追加され、エッジ形成サイクルかどうかがチェックされます。サイクルを形成する場合は、リストからエッジを破棄して次のエッジに進みます。

  2. データ構造の償却時間計算量

    償却分析 この分析は、時折の操作が非常に遅い場合に使用されますが、非常に頻繁に実行される操作のほとんどは高速です。データ構造では、ハッシュテーブル、互いに素なセットなどの償却分析が必要です。 ハッシュテーブルでは、ほとんどの場合、検索時間の複雑さはO（1）ですが、O（n）操作を実行することもあります。ほとんどの場合、ハッシュテーブルで要素を検索または挿入する場合、タスクは一定時間かかりますが、衝突が発生すると、衝突を解決するためにO（n）回の操作が必要になります。 集計方法 総コストを見つけるために集計方法が使用されます。大量のデータを追加する場合は、この式で償却原価を見つける必要があり