大o()时间表示法 Flashcards

1
Q

二分查找法与简单查找法时间的不同

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

常见O ( ) 类型

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

数组、链表 具象化表示

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

数组的不足之处

A

这就像你与朋友去看电影,找到地方就坐后又来了一位朋友,但原来坐的地方没有空位置,只得再找一个可坐下所有人的地方。在这种情况下,你需要请求计算机重新分配一块可容纳4个待办事项的内存,再将所有待办事项都移到那里。如果又来了一位朋友,而当前坐的地方也没有空位,你们就得再次转移!真是太麻烦了。同样,在数组中添加新元素也可能很麻烦。如果没有了空间,就得移到内存的其他地方,因此添加新元素的速度会很慢。一种解决之道是“预留座位”:即便当前只有3个待办事项,也请计算机提供10个位置,以防需要添加待办事项。这样,只要待办事项不超过10个,就无需转移。这是一个不错的权变措施,但你应该明白,

数组存在如下两个缺点
❑ 你额外请求的位置可能根本用不上,这将浪费内存。你没有使用,别人也用不了。
❑ 待办事项超过10个后,你还得转移。因此,这种权宜措施虽然不错,但绝非完美的解决方案。对于这种问题,可使用链表来解决。

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

链表的不足之处:读取速度慢

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

链表、数组 添加、读取 O ( )归纳

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

链表、数组 删除 O ( )归纳

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

旅行商问题所需时间

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly