知识卡片
首尾出入队的代价不同
尾部追加a = append(a, x)在不扩容时为常数工作,扩容还要复制;头部插入通常搬移全部元素。图示头部弹出x, a = a[0], a[1:]无需搬移,但仍可能保留整个数组;尾部弹出也只改长度。操作假设切片非空,持续排队还要管理引用与容量。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 切片(slice)性能及陷阱 · 查看原书依据
在末尾追加元素,不考虑内存拷贝的情况,复杂度为 O(1)。 在头部追加元素,时间和空间复杂度均为 O(N),不推荐。 2.8 Pop 尾部删除元素,复杂度 O(1) 头部删除元素,如果使用切片方式,复杂度为 O(1)。
参考来源
- 位置:《Go 语言高性能编程》第08章《切片(slice)性能及陷阱》(来源项目book-sources;源文件:extracted/Go 语言高性能编程/_epub-src/OEBPS/Text/08.html)
- 结论依据:尾部追加`a = append(a, x)`在不扩容时为常数工作,扩容还要复制;头部插入通常搬移全部元素。原文相应定义、示例或限制为此结论提供依据;补充纠错与版本边界在正文就近标明。
- 原始内容:在末尾追加元素,不考虑内存拷贝的情况,复杂度为 O(1)。 在头部追加元素,时间和空间复杂度均为 O(N),不推荐。 2.8 Pop 尾部删除元素,复杂度 O(1) 头部删除元素,如果使用切片方式,复杂度为 O(1)。