知识卡片

普通读书笔记卡 · 3603

传参策略改变递归成本

理解等级:中级

分析分治算法时,传递数组指针通常只需 Θ(1);

若按值复制完整 N 元素数组,每次调用多出 Θ(N),只复制将访问的 n 元素子范围则多出 Θ(n)。

同一算法在不同传参语义下递归式会改变,不能把“传数组”默认视为零成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.