l****u
发帖数: 1764 | 1 哪种数据结构search最高效？
我觉得是binary search tree，因为如果是balanced BST，O(lgN)的复杂度就能找到一
个element
哪种数据结构sort最高效？
这个我就不知道怎么答了，只听过哪种algorithm，没听过哪种数据结构的。基本上
sort一组数据，最快也得要O(NlgN)吧，用quick sort或者merge sort的话。但这几种
algorithm都能针对各种不止一种data structure吧，比如 array， ArrayList，
linkedlist
求大神指点 |
s**********g
发帖数: 14942 | 2 你这个完全得看application啊
time vs space tradeoff
search一般来说当然binary search是不错的
但hashset能搞出O(1)来，如果hash function很好的话
sort也要看要求啊
哪怕是algorithm，一般NlogN，但是mergesort和quicksort都有不同的应用
整数的话，甚至可以radix sort搞出O(N)
扯上结构的话，linkedlist就经常不是很好用，因为没有O(1) random access
那arraylist也许会比较方便
或者直接上heap
我觉得这种问题就是看你的理解深度，我不认为能简单一个回答解决，而应该看实际的
tradeoff
【在 l****u 的大作中提到】
: 哪种数据结构search最高效？
: 我觉得是binary search tree，因为如果是balanced BST，O(lgN)的复杂度就能找到一
: 个element
: 哪种数据结构sort最高效？
: 这个我就不知道怎么答了，只听过哪种algorithm，没听过哪种数据结构的。基本上
: sort一组数据，最快也得要O(NlgN)吧，用quick sort或者merge sort的话。但这几种
: algorithm都能针对各种不止一种data structure吧，比如 array， ArrayList，
: linkedlist
: 求大神指点
|
l****u
发帖数: 1764 | 3 我也觉得这问题没有一个统一答案。但如果非要选一个，是不是array就是最好的答案
了，因为几乎什么sort algorithm都能在array上很好的实现啊。当然，我觉得这其实
只是说明array只是最common的data structure而已。。
【在 s**********g 的大作中提到】
: 你这个完全得看application啊
: time vs space tradeoff
: search一般来说当然binary search是不错的
: 但hashset能搞出O(1)来，如果hash function很好的话
: sort也要看要求啊
: 哪怕是algorithm，一般NlogN，但是mergesort和quicksort都有不同的应用
: 整数的话，甚至可以radix sort搞出O(N)
: 扯上结构的话，linkedlist就经常不是很好用，因为没有O(1) random access
: 那arraylist也许会比较方便
: 或者直接上heap
|
b********6
发帖数: 35437 | 4 search最高效的是hash table, O(1) |
c********t
发帖数: 5706 | 5 非要选的话 我选search: hashtable
sort: heap or BST
【在 l****u 的大作中提到】
: 我也觉得这问题没有一个统一答案。但如果非要选一个，是不是array就是最好的答案
: 了，因为几乎什么sort algorithm都能在array上很好的实现啊。当然，我觉得这其实
: 只是说明array只是最common的data structure而已。。
|
l****u
发帖数: 1764 | 6 hashset就够了吧，也是O(1)
【在 b********6 的大作中提到】
: search最高效的是hash table, O(1)
|
