没有合适的资源?快使用搜索试试~ 我知道了~
rotated-array-set:具有O(lg n)访问权和O(√n)插入和删除的排序数组
共14个文件
svg:7个
rs:3个
toml:1个
需积分: 9 0 下载量 197 浏览量
2021-03-16
04:12:40
上传
评论
收藏 78KB ZIP 举报
温馨提示
旋转数组集 在Rust中实现的2级旋转阵列 该存储库包含“ 2级旋转数组”结构的实现,单元测试和基准代码,该结构最初发表于Munro和Suwanda的1979年论文 (还引入了众所周知的数据结构)。 在 (1983)和 (2001)中进一步开发和讨论了此结构。 (后者将概念推广到动态数组抽象数据类型,而不是排序数组。) 2级旋转数组相对于普通排序数组的理论优势在于,与O(n) O(√n)相比,它提供相同的搜索性能( O(log n) ),具有更好的插入和删除性能( O(√n) O(n) (排序后的数组),在完全相同的空间中(即,不超过数据本身)。 (对于纯隐式结构,插入和删除为O(√n * log n) ,但可以使用O(√n)多余的空间(可忽略的数量O(√n)将其减少为O(√n) 。此实现遵循这种方法。)这种O(√n)插入/删除性能比平衡树(例如,红黑树或B树)的O(log N)性能差很
资源推荐
资源详情
资源评论
收起资源包目录
rotated-array-set-master.zip (14个子文件)
rotated-array-set-master
.gitignore 29B
benches
my_benchmark.rs 7KB
src
lib.rs 59KB
Cargo.toml 559B
README.md 5KB
tests
proptests.rs 11KB
img
Remove_Vec.svg 33KB
Find_SortedVec.svg 31KB
Find_Vec.svg 31KB
Insert_SortedVec.svg 31KB
Remove_BTreeSet.svg 22KB
Find_BTreeSet.svg 17KB
cells.png 42KB
Remove_SortedVec.svg 31KB
共 14 条
- 1
资源评论
绘画窝
- 粉丝: 21
- 资源: 4715
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功