请构造个数据结构，满足： - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

请构造个数据结构，满足：

请构造个数据结构，满足：# Programming - 葵花宝典

h*o2007-10-16 07:10

1 楼

复杂度 of access: O(1)
复杂度 of insert: O(1)
复杂度 of delete: O(1)
复杂度 of traverse: = O(n)
不是 hash. 因为 hash 的复杂度 of traverse: >= O(n)

T*i2007-10-16 07:10

2 楼

hash with link-list

【在 h**o 的大作中提到】

: 复杂度 of access: O(1)
: 复杂度 of insert: O(1)
: 复杂度 of delete: O(1)
: 复杂度 of traverse: = O(n)
: 不是 hash. 因为 hash 的复杂度 of traverse: >= O(n)

k*f2007-10-16 07:10

3 楼

http://en.wikipedia.org/wiki/Heap_(data_structure)

【在 h**o 的大作中提到】

: 复杂度 of access: O(1)
: 复杂度 of insert: O(1)
: 复杂度 of delete: O(1)
: 复杂度 of traverse: = O(n)
: 不是 hash. 因为 hash 的复杂度 of traverse: >= O(n)

q*n2007-10-16 07:10

4 楼

a simple lookup table.

【在 h**o 的大作中提到】

: 复杂度 of access: O(1)
: 复杂度 of insert: O(1)
: 复杂度 of delete: O(1)
: 复杂度 of traverse: = O(n)
: 不是 hash. 因为 hash 的复杂度 of traverse: >= O(n)

c*t2007-10-16 07:10

5 楼

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Not really. Hash 的 ideal size 只是 n 的两倍左右。
还是在 O (n) 之内的。

【在 h**o 的大作中提到】

: 复杂度 of access: O(1)
: 复杂度 of insert: O(1)
: 复杂度 of delete: O(1)
: 复杂度 of traverse: = O(n)
: 不是 hash. 因为 hash 的复杂度 of traverse: >= O(n)

b*n2007-10-16 07:10

6 楼

人家就要n。

【在 c*****t 的大作中提到】

:
: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: Not really. Hash 的 ideal size 只是 n 的两倍左右。
: 还是在 O (n) 之内的。

b*n2007-10-16 07:10

7 楼

pool

【在 h**o 的大作中提到】

: 复杂度 of access: O(1)
: 复杂度 of insert: O(1)
: 复杂度 of delete: O(1)
: 复杂度 of traverse: = O(n)
: 不是 hash. 因为 hash 的复杂度 of traverse: >= O(n)

h*o2007-10-16 07:10

8 楼

谢谢大家恢复。
不知道其他答案对不对。我得学习一下。
不过hash+link list 肯定是个正确答案。
但我不懂，这个hash+link list 是指chaining hash 吗？
那最起码复杂度 of access() 就不是1啊。
特别如果chain很长，根list 没什么区别。

【在 b******n 的大作中提到】

: pool

t*t2007-10-16 07:10

9 楼

no.

【在 h**o 的大作中提到】

: 谢谢大家恢复。
: 不知道其他答案对不对。我得学习一下。
: 不过hash+link list 肯定是个正确答案。
: 但我不懂，这个hash+link list 是指chaining hash 吗？
: 那最起码复杂度 of access() 就不是1啊。
: 特别如果chain很长，根list 没什么区别。

S*n2007-10-16 07:10

10 楼

access还是用hash的hash function，所以还是O(1)
traverse用list，所以是O(n).

【在 h**o 的大作中提到】

h*o2007-10-16 07:10

11 楼

你是说除hash table 外另用一个link list吗？
那 insert 和 delete 就不是O(1)了，因为link list 里的内容也要变。
可能你是说把 hash (key, value) 的结构变成hash (key, value， *prev_node,*next
_node)吧？

【在 S*****n 的大作中提到】

:
: access还是用hash的hash function，所以还是O(1)
: traverse用list，所以是O(n).

t*t2007-10-16 07:10

12 楼

那请问,linked list的insert和delete是什么复杂度?

next

【在 h**o 的大作中提到】

: 你是说除hash table 外另用一个link list吗？
: 那 insert 和 delete 就不是O(1)了，因为link list 里的内容也要变。
: 可能你是说把 hash (key, value) 的结构变成hash (key, value， *prev_node,*next
: _node)吧？

h*o2007-10-16 07:10

13 楼

你是说O(1)啊。
可是难道不是先找到位置再delete/insert吗？
不好意思我太笨了。

【在 t****t 的大作中提到】

: 那请问,linked list的insert和delete是什么复杂度?
:
: next