滚烫的数据砖头电面

想到一个数据结构:

vector<list<int>>  v;

一个长度为N的数组A分成sqrt(N)段，存在v中
插入删除保持以上性质: 分成sqrt(N)段，每段有sqrt(N)个元素

时间复杂度分析:

query(i) : v[i / sqrt(N)][i - i/sqrt(N) * sqrt(N)]，时间复杂度O(sqrt(N))，因为是list
insert(i): 假如插入位置0，需要移动元素：1 +
                                                     (sqrt(N+1) - sqrt(N)) +
                                               2 * (sqrt(N+1) - sqrt(N)) +
                                               3 * (sqrt(N+1) - sqrt(N)) +
                                               ...
                                      sqrt(N) * (sqrt(N+1) - sqrt(N)) =
         (1 + sqrt(N)) * sqrt(N) / 2 * (sqrt(N+1) - sqrt(N)) = O(N/(sqrt(N+1) + sqrt(N)) = O(sqrt(N))

del(i):  假如删除位置0，需要移动元素：1 +                                                    (sqrt(N) - sqrt(N - 1)) +
                                               2 * (sqrt(N) - sqrt(N - 1)) +
                                               3 * (sqrt(N) - sqrt(N - 1)) +
                                               ...
                                      sqrt(N) * (sqrt(N) - sqrt(N - 1)) =
         (1 + sqrt(N)) * sqrt(N) / 2 * (sqrt(N) - sqrt(N - 1)) = O(N/(sqrt(N - 1) + sqrt(N)) = O(sqrt(N))


所以最坏复杂度O(sqrt(N)), which is sublinear

求大米

基本上就是  手写一个平衡树。。。

Map<Original_ID, ID_in_List> + List<Character> 不行吗？

tianlu1 发表于 2021-1-25 12:51
Map + List 不行吗？

O(n)的插入。显然不行

fatalme 发表于 2021-1-19 01:05
想到一个数据结构:

vector  v;

你这里sqrt(N) - sqrt(N - 1)接近于0了吧

fatalme 发表于 2021-1-19 01:05
想到一个数据结构:

vector  v;

有几个问题:
1. (1 + sqrt(N)) * sqrt(N) / 2 * (sqrt(N+1) - sqrt(N)) = O(N/(sqrt(N+1) + sqrt(N)), 这一步是怎么推导出来的, 可以详细解释一下吗?
2. 删除和插入的时候, 第一行的这个移动1个元素为什么呢?

metacpp1982 发表于 2021-4-14 06:38
有几个问题:
1. (1 + sqrt(N)) * sqrt(N) / 2 * (sqrt(N+1) - sqrt(N)) = O(N/(sqrt(N+1) + sqrt(N)),  ...

1. (a - b) = (a^2 - b^2)/(a + b)  因为初中的因式分解： a^2 - b^2 = (a + b) (a - b)
2. 推导不严格，可以插入任何一个位置，推导类似。结论不变。

fatalme 发表于 2021-4-14 11:57
1. (a - b) = (a^2 - b^2)/(a + b)  因为初中的因式分解： a^2 - b^2 = (a + b) (a - b)
2. 推导不严格 ...

原来如此, 很精妙.

插入/删除任何位置后, 从第一个block开始逐个移动元素进行调整, 根据公式, 每个block只需和下一个block之间进行元素相互移动吧.

metacpp1982 发表于 2021-4-14 14:40
原来如此, 很精妙.

插入/删除任何位置后, 从第一个block开始逐个移动元素进行调整, 根据公式, 每个blo ...

sqrt(N+1)  和 sqrt(N)要么相等要么多一，比如sqrt(100) = sqrt(99)+1，这样的话(sqrt(N+1) - sqrt(N))要么0要么1.

所以(1 + sqrt(N)) * sqrt(N) / 2 * (sqrt(N+1) - sqrt(N))就是(1 + sqrt(N)) * sqrt(N) / 2？也就是O(N)？

我一朋友从内部题库看到这题了，其实大家都被误导了。小提示：不要去实现什么平衡树了，用bucket算法就行，比如用个5个元素的bucket，那算法是O(N/5)。这就算sub-linear