1

最悪のケースの時間と平均ケースの時間の複雑さについて少し混乱しています。私の混乱の原因は ここにあります

私の目的は、昇順でデータを短縮することです。ソートのタスクを完了するために BST を選択します。ここでは、データを昇順で印刷するために行っていることを示します。

 1) Construct a binary search tree for given input.
        Time complexity: Avg Case O(log n)
                         Worst Case O(H) {H is height of tree, here we can Assume Height is equal to number of node H = n}

 2)After Finishing first work I am traversing BST in Inorder to print data in Increasing order. 
        Time complexity: O(n) {n is the number of nodes in tree}

Now  I analyzed total complexity for get my desire result (data in increasing order) is for Avg Case: T(n) = O(log n) +O(n) = max(log n, n) = O(n)
      For Worst Case : T(n) = O(n) +O(n) = max(n, n) = O(n)

上記の点は、上記のリンクの概念とは異なる私の理解でした。私は間違った解釈をしていることを知っています。私を修正してください。あなたの提案と考えをいただければ幸いです。

私が言及したスライドの下にあるこのタイトルを参照してください。 ここに画像の説明を入力

4

2 に答える 2

1

(1) では、要素ごとの時間を指定します。要素の数を掛ける必要があります。

于 2012-05-22T14:13:31.107 に答える
1

二分木を構築するために必要な時間の複雑さは、各ノードを挿入する必要があるため、提案した複雑さの n 倍です。

于 2012-05-22T14:13:44.610 に答える