c***g
发帖数: 472 | 1 what's the downside of the sigleton?
what's the downside of the binary search tree compared to linked list? |
g**e
发帖数: 6127 | 2
1. development confusion
2. unite test difficulty
3. possible throughput problem with multithread program
4. slightly overhead for checking instance existance every time
1. worst case BST degenerates to a linked list
2. O(logn) insert/delete time
3. conding complexity
【在 c***g 的大作中提到】
: what's the downside of the sigleton?
: what's the downside of the binary search tree compared to linked list?
|
c*********t
发帖数: 2921 | 3 我觉得对于linked list，
insert： 如果加到头，O(1); 如果要求加到某个有特定的key 的Node后的话，要从头
开始search到要加的位置，这时就是O(n)了。
delete: 如果给了那个node的指针，delete O(1); 可是如果只告诉你删除有某个给定
的key的那个Node,就是O(n).
【在 g**e 的大作中提到】
:
: 1. development confusion
: 2. unite test difficulty
: 3. possible throughput problem with multithread program
: 4. slightly overhead for checking instance existance every time
: 1. worst case BST degenerates to a linked list
: 2. O(logn) insert/delete time
: 3. conding complexity
|
m**q
发帖数: 189 | 4 For BST, it uses more spaces than linked list - two pointers per entry
compared to one.
【在 g**e 的大作中提到】
:
: 1. development confusion
: 2. unite test difficulty
: 3. possible throughput problem with multithread program
: 4. slightly overhead for checking instance existance every time
: 1. worst case BST degenerates to a linked list
: 2. O(logn) insert/delete time
: 3. conding complexity
|
