-6

以未排序的方式给定数字说 X：{4,2,5,1,8,2,7}

你如何找到数字的排名？

例如：4:4 的排名：5:5 的排名

复杂度必须为 O(lg n)。

借助红黑树和增强数据结构方法（当今令人着迷的东西之一），它可以在 O(lg n) 的复杂性中完成。让我们使用订单统计树Order Statistic Tree

Algorithm:
RANK(T,x)

//T: order-statistic tree, x: node(to find rank of this node)
r = x.left.size + 1
y=x
While y != T.root
    if y==y.p.right
        r= + y.p.left.size + 1
    y=y.p
Return r;

任何帮助表示赞赏。

还有比这更好的方法吗？

4

1 回答 1

2

以未排序的方式给定数字，比如说X:{4,2,5,1,8,2,7}

你如何找到数字的排名？

Rank 是元素在排序时的位置。

复杂度必须为 O(lg n)。

这不可能。您必须至少查看每个元素一次。因此，你不能比 更好O(n)，而且在 O(n) 中是微不足道的：

  • 设置found为false
  • 设置smaller为 0
  • 对于每个数字array
    • 如果数字小于needle
      • 增加较小的计数器
    • 如果数字等于needle
      • 设置found为true
  • 如果found，返回smaller+1，否则返回错误

借助红黑树和增强数据结构方法（当今令人着迷的东西之一），它可以在 O(lg n) 的复杂性中完成。让我们利用订单统计树

问题是您没有订单统计树，而且您没有时间构建一个。构建顺序统计树需要的不仅仅是O(lg n)时间*。

但是，假设您有时间构建一个订单统计树。由于在二叉搜索树中提取已排序的节点列表需要线性时间，因此构建顺序统计树不能比直接排序数组更快。

所以，让我们直接对数组进行排序。那么，求一个元素的秩就相当于在一个有序数组中求该元素。这是一个众所周知的任务，可以O(lg n)通过二分搜索来解决（反复将数组分成两半，直到找到元素）。事实证明，顺序统计树完全没有帮助。实际上，您可以将二分查找想象为在顺序统计树中的查找（除了该树实际上并不存在）。

如果x可以在运行时更改，那么顺序统计树确实会有所帮助。然后，元素删除/添加需要Th(lg n)（最坏情况）时间，而Th(n)在普通排序数组中需要 *（平均情况），因为您需要移动元素。使用x不可变的顺序统计树不会加快普通数组的速度。

* 从技术上讲，O(lg n)是一组渐近增长不超过lg n. 当我说“超过O(lg n)”时，正确的解释是“超过 . 中的每个函数O(lg n)。顺便说一下，这相当于说运行时是omega(lg n)（注意欧米茄是小写的）。

Th(lg n)是渐近等于 的函数集lg n，直到一个常数。在保持技术正确的同时使用 O(lg n) 和英语表达相同的意思会很尴尬。

于 2013-03-04T10:56:16.710 回答