用代码来作为例子,假设我们的数据结构名为 MagicArray:
magic_array = MagicArray("How are you", "I am find", "Thank you", "And you")
print(magic_array[2]) # 这一行应该打印 "Thank you",且该行的运行时间应该与 magic_array 的长度无关,或者至少“摊还地”无关.
magic_array.remove(1) # 这一行的运行时间应该与 magic_array 的长度无关,或者至少“摊还地”无关.
print(magic_array[2]) # 这一行应该打印 "And you",且该行的运行时间应该与 magic_array 的长度无关,或者至少“摊还地”无关.
如果我们无法设计出这样的数据结构,我们如何形式证明它不可能存在?如果确实不可能存在,我们可以设计出的最接近它的最快的数据结构能够有多快?
1
xupefei 2021-01-07 21:28:06 +08:00 via iPhone
链表+位置到节点的哈希表。
这题算是 leetcode 中等难度。 |
2
php8 2021-01-07 21:28:42 +08:00 via Android
咱 php 数组插入和删除都是 O(1)滴,还能当 map 用,难怪被公认是最好的语言
|
3
xupefei 2021-01-07 21:33:10 +08:00 via iPhone
@xupefei 不过我这个办法删除比 O1 复杂,最坏情况下是 On 。
用 jumplist 可能会更好 |
4
littleMaple OP @xupefei #1 删除操作的时候维护「位置映射到节点的哈希表」就需要 O(n) 的复杂度吧?例如 magic_array.remove(1) 操作运行的时候,2->"Thank you" 和 3->"And you" 这两个映射就需要更新成 1->"Thank you" 和 2->"And you"。
|
5
xupefei 2021-01-07 21:36:17 +08:00 via iPhone 1
最好的办法应该是用 rope,能做到 logn 复杂度
|
6
sunkai0609 2021-01-07 22:06:26 +08:00
php 的数组
|
7
sunkai0609 2021-01-07 22:07:54 +08:00
@sunkai0609 请无视我
|
8
hanxiV2EX 2021-01-07 22:10:50 +08:00 via Android 1
跳跃表,redis 的 zset
只能做到 lgn |
9
love 2021-01-07 23:18:15 +08:00 via Android
这和 map 用整数做 key 有什么区别?
|
10
mxT52CRuqR6o5 2021-01-07 23:41:16 +08:00 via Android
@php8 我 google 了一下 php 的 array_splice 可并不是 O(1)而是 O(offset+length)啊
|
11
mxT52CRuqR6o5 2021-01-07 23:42:31 +08:00 via Android 1
这个问题一两句应该证明不了,书上也许会有答案
|
12
raaaaaar 2021-01-07 23:55:06 +08:00 via Android 1
结合链表的增删和数组的查改优点就是跳表,所以不可能存在你说得这种上界都是 O(1) 的。
查找操作最好的就是利用内存的随机存取特点,但是要实现删除操作就必然和随机存取冲突,因为删除节点内存就变了,地址也变了,要不影响随机存取,内存肯定要移动的。 |
13
littleMaple OP @love #9 因为要求是 arraylike,例如如果删除了第三个元素,第四个元素至最后一个元素对应的索引都要相应的减一.
|
14
littleMaple OP @raaaaaar #12 确实如此,直观上来说 O(1) access 和 O(1) remove 不可能同时满足,但是若是 amortized O(1) access 和 amortized O(1) remove 呢?放宽一点要求之后不知道能不能同时满足.
|
15
php8 2021-01-08 00:50:39 +08:00 via Android
@mxT52CRuqR6o5 是我理解有误,没有考虑到删除之后下标要依次挪一格
|
16
wangxiyu191 2021-01-08 01:51:39 +08:00 2
没要求插入的时间和空间复杂度,钻个空子。可以在初始化 /插入时就生成好一次或多次删除后可能达到的所有的状态。这样插入和删除就都能做 O(1) 了。
|
17
wangxiyu191 2021-01-08 01:53:12 +08:00
@wangxiyu191 上面最后一句打错。“这样插入和删除就都能做 O(1) 了” -》 “这样查询和删除就都能做 O(1) 了”
|
18
sunnybird 2021-01-08 02:14:16 +08:00 via Android
算法核心思想,空间换时间
|
19
shiji 2021-01-08 02:42:37 +08:00 via iPhone
@littleMaple Hashmap 的核心不就是 array 么。 又没有必要说 array 不能留空,必须一字排开
|
20
littleMaple OP @wangxiyu191 #16 你居然能想到这样暴力的方案 XD 而且居然是对的.
|
21
littleMaple OP @shiji #19 我说的 arraylike 不是这个意思,你可以看我写在标题里的那一段代码,这个数据结构应该要能够满足那里描述的行为.
|
22
ericls 2021-01-08 03:17:53 +08:00 via iPhone
那就让插入贵一点嘛
|