复杂度为 O(sqrt(n)) 的链表中删除/插入/检索元素的算法
我们的任务是实现一个链表类，以 O(sqrt(n)) 的时间复杂度执行以下操作：
- 在第 i 个位置插入一个元素，
- 在第 i 个位置删除一个元素，
- 检索列表中的第 i 个元素。
我发现了一些数据结构，例如跳过列表。但时间复杂度应该是O(sqrt(n))。
任何人都可以帮忙吗？
our assignment is to implement a linked list class to do the following with time complexity of O(sqrt(n)):
- insert an element at i th place
- delete an element at i th place
- retrive i th element of the list.
I found a few data structures like skip list. but the time complexity should be O(sqrt(n)).
anyone can help?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您在理解 Big O 表示法时遇到了一些困难吗？
请记住，大 O 的意思是“上限”。
数学上，
f(x) = O( g(x) )iff(x) <= C ( g(x) )。这意味着，我们可以说
f(x) 是 O(x^2)并且f(x) 是 O(x^1000000000)，因为O (x^2)和O(x^1000000000)都是上限（尽管不一定是“好的”上限）。现在，正如您所研究的，跳过列表的时间是 O(log n) 。
这意味着因为 log(n)
log(n)log(n)log(n)log(n)log(n)sqrt(n) ，我们可以说跳过列表也是
O( sqrt(n) )。Are you having a little trouble understanding the Big O notation?
Remember, Big O means "Upper Bound".
Mathematically,
f(x) = O( g(x) )iff(x) <= C ( g(x) ).That means, we can say that
f(x) is O(x^2)andf(x) is O(x^1000000000), becauseO(x^2)andO(x^1000000000)are both upper bounds (though, not necessarily "good" upper bounds).Now, Skip Lists are O(log n) time, as you researched.
That means because
log(n) < sqrt(n),we can say that Skip Lists are also
O( sqrt(n) ).跳跃列表的搜索、删除和插入的复杂度
O(log n)，因此它们满足您的要求。请记住，任何O(log n)的函数也是O(sqrt(N))，因为sqrt的渐近增长速度比>日志。Skip lists have complexity
O(log n)for search, deletion and insertion, so they satisfy your requirement. Remember that any function that isO(log n)is alsoO(sqrt(N)), becausesqrtgrows asymptotically faster thanlog.看起来这应该可以通过仅使用两个链接列表的跳过列表思想的简化版本来实现。但是您需要巧妙地使用算法，以确保较短列表中元素的最大数量以
O(sqrt(N))为界，以及较长列表中元素之间的最大距离较短列表的相邻元素也受O(sqrt(N))限制。It seems like this should be doable with a simplified version of the skip list idea using only two linked lists. But you would need to be somewhat clever with the algorithms to make sure that the maximum number of elements in the shorter list is bounded by
O(sqrt(N))and the maximum distance in the longer list between adjacent elements of the shorter list is also bounded byO(sqrt(N)).