知识卡片
相邻斐波那契数使辗转相除最慢
欧几里得算法递归次数随较小输入b的位数线性增长;相邻斐波那契数恰达到文中的递归次数上界。
对β位输入,书中由每次算术O(β²)得O(β³)位操作上界,另提示可改进。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第31章 数论算法 · 查看原书依据
Since Fk is approximately , where ϕ is the golden ratio defined by equation (3.32) on page 69, the number of recursive calls in EUCLID is O(1g b). (See Exercise 31.2-5 for a tighter bound.) Therefore, a call of EUCLID on two β-bit numbers performs O(β) arithmetic operations and O(β3) bit operations (assuming that multiplication and division of β-bit numbers take
参考来源
- 位置:《算法导论(第4版)》第31章《数论算法》(OEBPS/chapter031.xhtml,文本字符[20000,25000))。
- 结论依据:原文给出最大公约数递推、扩展算法或模运算群的定义和证明;公式图已核对。
- 原始内容:Since F k is approximately , where ϕ is the golden ratio defined by equation (3.32) on page 69, the number of recursive calls in E UCLID is O (1g b ). (See Exercise 31.2-5 for a tighter bound.) Therefore, a call of E UCLID on two β -bit numbers performs O ( β ) arithmetic operations and O ( β 3 ) bit operations (assuming that multiplication and division of β -bit numbers take