这是我感到很疑问的一个问题
说要我们求得 一个无序集合中的第i小的数
显然可以这样,先将集合中的数排序,然后再直接取出第i小的即可,这样最好效率为O(nlgn)
当然 人们说还有一种更好的办法就是 使用扩张后的红黑树,查找效率为O(lgn),但是就整个程序来说 考虑算法复杂度时 ,不应该将构造红黑树的时间也算进去吗? 这样总的一来 效率不见得比直接排序 来的好啊?
显然可以这样,先将集合中的数排序,然后再直接取出第i小的即可,这样最好效率为O(nlgn)
当然 人们说还有一种更好的办法就是 使用扩张后的红黑树,查找效率为O(lgn),但是就整个程序来说 考虑算法复杂度时 ,不应该将构造红黑树的时间也算进去吗? 这样总的一来 效率不见得比直接排序 来的好啊?
作者: sina2008you 发布时间: 2011-06-12
没听说过取第i小能低于O(n)的
作者: sbwwkmyd 发布时间: 2011-06-12