14

在 a 上插入的最坏情况运行时间red-black tree是O(lg n)，如果我in-order walk在树上执行 a，我基本上会访问每个节点，因此打印排序集合的总最坏情况运行时间将是 O(n lg n)

我很好奇，为什么red-black trees不首选排序quick sort（其平均案例运行时间为O(n lg n).

我看到这可能是因为red-black trees没有就地排序，但我不确定，所以也许有人可以提供帮助。

4

6 回答 6

10

了解哪种排序算法性能更好实际上取决于您的数据和情况。

如果您用一般/实用的术语说话，

快速排序（您随机选择枢轴/只选择一个固定的枢轴，使最坏的情况欧米茄（n ^ 2））可能比红黑树更好，因为（不一定按重要性顺序）

  • 快速排序是就地的。保持你的内存占用低。假设这个快速排序例程是处理大量数据的程序的一部分。如果您继续使用大量内存，您的操作系统可能会开始交换您的进程内存并破坏您的性能。

  • 快速排序内存访问是本地化的。这与缓存/交换配合得很好。

  • Quicksort can be easily parallelized (probably more relevant these days).

  • If you were to try and optimize binary tree sorting (using binary tree without balancing) by using an array instead, you will end up doing something like Quicksort!

  • Red-Black trees have memory overheads. You have to allocate nodes possibly multiple times, your memory requirements with trees is doubles/triple that using arrays.

  • After sorting, say you wanted the 1045th (say) element, you will need to maintain order statistics in your tree (extra memory cost because of this) and you will have O(logn) access time!

  • Red-black trees have overheads just to access the next element (pointer lookups)

  • Red-black trees do not play well with the cache and the pointer accesses could induce more swapping.

  • Rotation in red-black trees will increase the constant factor in the O(nlogn).

  • Perhaps the most important reason (but not valid if you have lib etc available), Quicksort is very simple to understand and implement. Even a school kid can understand it!

I would say you try to measure both implementations and see what happens!

Also, Bob Sedgewick did a thesis on quicksort! Might be worth reading.

于 2010-07-17T14:25:05.630 回答
2

有很多排序算法是最坏的情况O(n log n)——例如，归并排序。首选快速排序的原因是因为它在实践中更快，即使在算法上它可能不如其他一些算法好。

通常，内置排序根据 n 的值使用各种方法的组合。

于 2010-07-17T06:53:11.220 回答
1

There are many cases where red-back trees are not bad for sorting. My testing showed, compared to natural merge sort, that red-black trees excel where:

Trees are better for Dups: All the tests where dups need to be eleminated, tree algorithm is better. This is not astonishing, since the tree can be kept very small from the beginning, whereby algorithms that are designed for inline array sort might pass around larger segments for a longer time.

Trees are better for Random: All the tests with random, tree algorithm is better. This is also not astonishing, since in a tree distance between elements is shorter and shifting is not necessary. So repeatedly inserting into a tree could need less effort than sorting an array.

So we get the impression that the natural merge sort only excels in ascending and descending special cases. Which cant be even said for quick sort.

Gist with the test cases here.

P.S.: it should be noted that using trees for sorting is non-trivial. One has not only to provide an insert routine but also a routine that can linearize the tree back to an array. We are currently using a get_last and a predecessor routine, which doesn't need a stack. But these routines are not O(1) since they contain loops.

于 2015-10-28T00:12:37.610 回答
0

Big-O 时间复杂度度量通常不考虑标量因素，例如，O(2n) 和 O(4n) 通常只是简化为 O(n)。时间复杂度分析基于算法级别的操作步骤，而不是严格的编程级别，即没有源代码或本地机器指令考虑。

快速排序通常比基于树的排序更快，因为 (1) 这些方法具有相同的算法平均时间复杂度，以及 (2) 与使用红黑树相比，使用简单数组时查找和交换操作需要更少的程序命令和数据访问，即使树使用底层的基于数组的实现。维护红黑树约束需要额外的操作步骤、数据字段值存储/访​​问（节点颜色）等，而不是快速排序的简单数组分区交换步骤。

最终结果是红黑树比快速排序具有更高的标量系数，这被标准 O(n log n) 平均时间复杂度分析结果所掩盖。

与机器架构相关的其他一些实际考虑在 Wikipedia 上的 Quicksort 文章中进行了简要讨论

于 2010-07-17T12:51:39.727 回答
0

Generally, representations of O(nlgn) algorithms can be expanded to A*nlgn + B where A and B are constants. There are many algorithmic proofs that show the coefficients for quicksort are smaller than those of other algorithms. That is in best-case (quick sort performs horribly on sorted data).

于 2010-07-17T14:29:04.620 回答
0

Hi the best way to explain the difference between all sorting routine in my opinion is. (My answer is for people who are confused how quick sort is faster in practice than another sorting algo).

"Think u are running on a very slow computer".

  1. First thing one comparing operation takes 1 hour.
  2. One shifting operation takes 2 hours.

"I am using hour just to make people understand how important time is".

Now from all the sorting operations quick-sort have very very less comparisons and very less swapping for elements.

Quick-sort is faster for this main reason.

于 2013-01-06T19:49:01.087 回答