algorithm - 平衡搜索树查询，渐近分析

Question

情况如下:-

We have n number and we have print them in sorted order. We have access to balanced dictionary data structure, which supports the operations serach, insert, delete, minimum, maximum each in O(log n) time.

We want to retrieve the numbers in sorted order in O(n log n) time using only the insert and in-order traversal.

这个问题的答案是:-

Sort()
  initialize(t)
  while(not EOF)
     read(x)
     insert(x,t);
  Traverse(t);

现在的查询是如果我们在时间“n”中读取元素，然后在“log n”(有序遍历)时间内遍历元素，那么这个算法的总时间为(n+logn)次，根据我的说法..请解释一下这个算法的后续计算时间..它如何在 O(nlogn) 时间内对列表进行排序？？

谢谢。

Answer 1

每次插入都是O(log n)。您正在执行 n 插入，因此给出 n * O(log n) = O(n log n) 渐近时间复杂度。遍历树是O(n)，因为有n个节点。这加起来为 O(n + n log n)，与 O(n log n) 相差一个常数，因此最终的渐近复杂度为 O( n log n)..

and then traverse the elements in "log n

遍历是O(n)，而不是O(log n)。一次插入是 O(log n)，而您正在执行 n 个这样的插入。