假设计算连分数展开式，常识算法是取小数部分，求逆，将下一项作为整数部分，对小数部分重复该过程。
但是，该算法具有顺序复杂性假设乘法。什么是渐近更快的算法？
是否有从十进制数字计算连分数展开的有效算法？
计算科学
算法
复杂
2021-12-12 05:35:54
1个回答
我还没有解决这个确切的问题，但附近的一个问题是找到小数的有理逼近（例如 0.333 => 1/3），为此我使用了一种称为“中间搜索”的算法。在幕后，这个搜索遍历了一个称为“Stern-Brocot 树”的（隐式/无限）数据结构，这是一种按排序顺序枚举每个可能的有理数的新方法。如果您在 Wikipedia 上查找这些术语，似乎有类似的基于 Stern-Brocot 的算法来查找连分数。