带倍增的链表,关于复杂度的的想法
  • 板块学术版
  • 楼主Asakawa_Luka
  • 当前回复21
  • 已保存回复21
  • 发布时间2022/8/22 08:52
  • 上次更新2023/10/27 14:14:08
查看原帖
带倍增的链表,关于复杂度的的想法
321898
Asakawa_Luka楼主2022/8/22 08:52

单次 insert(含 push_front、push_back)、erase(含 pop_front、pop_back)是 O(log2n)O(log_{2}n).

在结点里存下 202^0212^1等等结点指针,所以查询最多 O(log2n)O(log_{2}n).

加一个类似于 deque 的东西,访问元素的时候顺带更新,下一次访问变成 O(1)O(1).

还是很 naive&simple 的想法,应当有很大完善空间。

2022/8/22 08:52
加载中...