0

バイナリ ヒープ構造を含む次のアルゴリズムを実行しました。

Algorithm: heapMinimum(node)
Input    : Position n
Output   : Sequence minList; containing the postions that hold the minimum value

1. minList <-- sequence
2. if parent(node) == NULL // current node is the root of the tree
3.   minList.insertLast(node)
4. if (leftchild(node).element() == node.element())
5.   concat(heapMinimum(leftchild(node), minList))
6. if(right(node).element() == node.element())
7.   concat(heapMinimum(rightChild(node), minList))
8. return minList

アルゴリズムが行うことは、基本的に、ルートを指定して Binary Heap をトラバースし、最小値 (つまり、ルートの値と一致する値) を保持するノードを見つけて格納することです。

現在、アルゴリズムの実行時間を Big O 表記で計算するのに問題があります。私が混乱している理由は、各ノードの左右の子をトラバースするために使用される再帰のためです。

O(1)を除くすべての操作は一定時間で実行されconcatます。しかし、このような再帰的なソリューションの実行時間を正確に計算するにはどうすればよいでしょうか?

4

4 に答える 4

4

私には O(N) のように見えます。N は要素の数です。ヒープに等しい要素しか含まれていない場合、すべての要素がトラバースされます。また、concat O(1) ではないのはなぜですか? 数値を「連結」している限り、それも O(1) である必要があります。ただし、何らかの形で concat が O(N) である場合 (疑似コードからはそのように見えますが、返された 2 つのリストを連結する必要があるかどうかを再検討する必要があります)、合計時間は最悪の場合O(N 2 ) になります。

于 2010-02-20T15:22:24.173 に答える
1

バイナリヒープについて話していると思いますか？

ヒープ プロパティの定義により、ルートよりも大きな要素が見つかるまで再帰する必要があります。ただし、ツリーの現在のレベルにある他の要素がルートと同じサイズでないことも確認する必要があります。基本的に、これは、ルートより大きいヒープの要素に遭遇すると、その要素の子に再帰する必要がないという規則をもたらします。

ただし、最悪の場合、各要素がルートに等しい場合もあります。この場合、ヒープ全体をチェックする必要があり、O(n) 時間になります。ここで、n はヒープ内の要素の数です。

あなたの質問に答えるには、それはO(n)です

于 2010-02-20T15:22:32.563 に答える
0

ソリューションにバグがあると思います。最初のチェック:

親 (ノード) == NULL の場合

削除する必要がありますが、ノード != NULLのチェックを追加する必要があります。

さらに、リストを追加のパラメーターとして使用して、答えを入力することをお勧めします。だから、それは私の実装です：

Algorithm: heapMinimum(node, minList)
if (node != NULL)
{
   if (minList.empty() || minList.getFirst().element() == node.element())
   {
      minList.insertLast(node)

      heapMinimum(left(node),  minList)
      heapMinimum(right(node), minList)
   }
}

リストに要素を追加すると O(1) かかると仮定すると、関数は O(k) かかることがわかります。ここで、k はヒープ内の最小値の数です。

楽しみ。

于 2010-02-23T15:13:16.077 に答える
0

他の人が述べたように、 concat() が O(1) の場合 [そうでない場合は、そうすることができます]、アルゴリズムは出力のサイズで O(N) です。

ただし、リストをコピーする concat() を使用した場合 (システムによっては、これを誤って実行しやすい場合があります)、最悪の場合、出力のサイズは O(N^2) になります。この動作の原因となるケースは、concat() が各レベルでリストをコピーし続けるように、最小ノードがツリーの奥深くにある場合です。

この深さはヒープの深さによって制限されることに注意してください。したがって、ツリーのバランスが取れている場合、この最悪のケースもデータ構造のサイズで O(M log M) になります。コピーの最大数がツリーの深さであるため、これを見ることができます。

于 2010-02-20T18:42:16.583 に答える