这是我感到很疑问的一个问题

说要我们求得 一个无序集合中的第i小的数
显然可以这样,先将集合中的数排序,然后再直接取出第i小的即可,这样最好效率为O(nlgn)
当然 人们说还有一种更好的办法就是 使用扩张后的红黑树,查找效率为O(lgn),但是就整个程序来说 考虑算法复杂度时 ,不应该将构造红黑树的时间也算进去吗? 这样总的一来 效率不见得比直接排序 来的好啊?

作者: sina2008you   发布时间: 2011-06-12

没听说过取第i小能低于O(n)的

作者: sbwwkmyd   发布时间: 2011-06-12