知识卡片

普通读书笔记卡 · 3634.a.6.c.1

逆增长函数取达到阈值的最低层

理解等级:高级

快速增长函数族从 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。它增长极慢,却不是常数函数。

这张卡片看不懂?

已有反馈 · 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.