我们的任务是实现一个链表类来执行以下操作，时间复杂度为 O(sqrt(n)):
- 在第i个位置插入一个元素
- 删除第i个元素
- 检索列表的第 i 个元素。
我发现了一些数据结构，比如跳表。但是时间复杂度应该是O(sqrt(n))。
有人可以帮忙吗？
最佳答案
您是否在理解大 O 表示法时遇到了一些困难？
请记住，大 O 的意思是“上限”。
数学上，f(x) = O( g(x) ) 如果 f(x) <= C ( g(x) ) .
也就是说，我们可以说 f(x) is O(x^2)和 f(x) is O(x^1000000000) ，因为 O(x^2)和 O(x^1000000000)都是上限(尽管不一定是“好”上限)。
现在，正如您研究的那样，跳过列表是 O(log n) 时间。
这意味着因为log(n) < sqrt(n) ,
我们可以说跳过列表也是O( sqrt(n) ) .
关于在具有 O(sqrt(n)) 复杂度的链表中删除/插入/检索元素的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4072691/