知识卡片
逆增长函数取达到阈值的最低层
快速增长函数族从 A₀(j)=j+1 开始;更高层 Ak 会把前一层 A{k−1} 从 j 出发反复应用 j+1 次。仅看输入 1,便有 A₀(1)=2、A₁(1)=3、A₂(1)=7、A₃(1)=2047,而 A₄(1) 已远超常见规模。
α(n)=min{k:A_k(1)≥n},即达到阈值 n 所需的最低层。例如 n=7 时 α(n)=2,8≤n≤2047 时 α(n)=3。它增长极慢,却不是常数函数。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
In words, α(n) is the lowest level k for which Ak(1) is at least n. From the above values of Ak(1), we see that It is only for values of n so large that the term “astronomical” understates them (greater than A4(1), a huge number) that α(n) > 4, and so α(n) ≤ 4 for all practical purposes.
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[20000,25000))。
- 结论依据:原文式(19.1)定义 A₀ 及高层函数迭代,随后算出 A₀(1)=2、A₁(1)=3、A₂(1)=7、A₃(1)=2047;式(19.2)再把 α(n) 定义为首次达到 n 的最低层。正文数值演算直接使用这些原书数值。
- 原始内容:In words, α ( n ) is the lowest level k for which A k (1) is at least n . From the above values of A k (1), we see that It is only for values of n so large that the term “astronomical” understates them (greater than A 4 (1), a huge number) that α ( n ) > 4, and so α ( n ) ≤ 4 for all practical purposes.