知识卡片
迭代函数计数达到阈值的次数
先定义 f^(0)(n)=n,f^(i)(n) 表示从 n 开始连续应用 f 共 i 次。给定阈值 c,迭代函数 f_c^*(n) 是满足 f^(i)(n)≤c 的最小非负整数 i;如果不存在这样的 i,结果未定义。
补充教学演示:取 f(n)=n/2、c=1、n=8,依次得到 8→4→2→1,所以 f_1^*(8)=3。这个记号计数的是“达到阈值要迭代几次”,不是第 i 次迭代后的函数值。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
If there is no i such that f(i)(n) ≤ c, write “undefined” as your answer.
参考来源
- 位置:《算法导论(第4版)》第3章《运行时间的刻画》(OEBPS/chapter003.xhtml,文本字符[45000,47339))。
- 结论依据:问题3-7的 Art_P90–P92 先定义 `f^(i)(n)`,再把 `f_c^*(n)` 定义为使 `f^(i)(n)≤c` 的最小迭代次数;正文明确无法达到阈值时记 undefined。正文中的 `n/2` 数值演算是依据该定义补充的教学演示,不是书中案例或实测结果。
- 原始内容:If there is no i such that f ( i ) ( n ) ≤ c , write “undefined” as your answer.