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 回答