知识卡片
传参策略改变递归成本
分析分治算法时,传递数组指针通常只需 Θ(1);
若按值复制完整 N 元素数组,每次调用多出 Θ(N),只复制将访问的 n 元素子范围则多出 Θ(n)。
同一算法在不同传参语义下递归式会改变,不能把“传数组”默认视为零成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
This assumption is valid in most systems because a pointer to the array is passed, not the array itself.
参考来源
- 位置:《算法导论(第4版)》第 4 章 Problems 与 Chapter notes(`OEBPS/chapter004.xhtml`,文本字符 [85000, 90000);相关公式图 Art_P231–P244)。
- 结论依据:问题 4-2 将指针传递、复制全部 N 元素和仅复制子区间分别列为 Θ(1)、Θ(N)、Θ(n),因此同一分治流程会有不同非递归成本。
- 原始内容:This assumption is valid in most systems because a pointer to the array is passed, not the array itself.