c# - 关于比奈公式的小知识

Question

为什么 Binet 公式(O(LogN)，但不完全是)在时间上比迭代方法(O(n))更差？

static double SQRT5 = Math.Sqrt(5);
static double PHI = (SQRT5 + 1) / 2;
public static int Bine(int n)
{
    return (int)(Math.Pow(PHI, n) / SQRT5 + 0.5);
}

static long[] NumbersFibonacci = new long[35];
public static void Iteracii(int n)
{
NumbersFibonacci[0] = 0;
NumbersFibonacci[1] = 1;
for (int i = 1; i < n - 1; i++)
    {
        NumbersFibonacci[i + 1] = NumbersFibonacci[i] + NumbersFibonacci[i - 1];
    }
}

The time of the algorithms

Answer 1

如果假设算术运算为 O(1)，则使用 Binet 公式为 O(1)，典型的迭代实现为 O(n)。

但是，如果我们假设算术运算的复杂度为 O(1)，那么即使 fibo(n) 是一个常见的面试和电话屏幕主题，它实际上也没什么用以典型方式实现它是有意义的——除非被告知我们要忽略标准编程语言整数和 float 的有限性。斐波那契数呈指数增长。在选择的特定算法重要之前很久，它们就溢出了标准编程语言类型，只要那个算法没有选择朴素的递归实现。

具体来说，这里有两种在 C# 中返回第 n 个斐波纳契数的实现。最上面的一个实现了 Binet 对 double 的封闭形式解决方案并强制转换为 long，在 C# 中它将是 64 位宽。第二个是迭代版本:

static long constant_time_fibo(long n)
{
    double sqrt_of_five = Math.Sqrt(5.0);
    return (long) (
        (Math.Pow(1.0 + sqrt_of_five, n) - Math.Pow(1.0 - sqrt_of_five, n)) /
        (sqrt_of_five * Math.Pow(2.0, n))
    );
}
 
static long linear_time_fibo(long n)
{
    long previous = 0;
    long current = 1;
    for (int i = 1; i < n; i++)
    {
        long temp = current;
        current = previous + current;
        previous = temp;
    }
    return current;
}
 
static void Main(string[] args)
{
    for (int i = 1; i < 100; i++)
        Console.WriteLine("{0} => {1} {2}", i, 
            constant_time_fibo(i), linear_time_fibo(i) );
}

当我运行这段代码时，由于浮点错误，常数时间算法在 n = 72 左右无法匹配迭代实现，并且由于溢出，迭代方法在 n = 92 时失败。如果我使用 32 位类型而不是 64 位类型，这会发生得更快。

九十二项算不了什么。如果你在实践中需要第 n 个斐波那契数并且只关心适合 64 位的斐波那契数，在非人为的情况下——不是为了家庭作业或白板问题——它应该花费 O(1) 时间而不是因为 Binet 公式的存在，但因为您应该使用其中包含 92 项的查找表。在 C++ 中，您甚至可以在编译时使用 constexpr 函数生成 92 项。

另一方面，如果我们谈论的是任意大数算术，那么这个问题就更有趣了。比奈公式中的指数都是整数。你可以只使用任意大的整数运算来实现 Binet 的公式——你不需要计算 5 的任何平方根，只需要跟踪“5 的平方根在哪里”，因为它们最终会抵消。您根据像 (a+b√5)/c 这样的二项式形式进行计算，但由于 ϕ 的怪异代数性质，所有无理数和所有非整数数学都被魔法抵消了。求 ϕ^n 时不需要实际计算任何 √5。如果您使用“exponentiation by squaring ” 这将导致 O(log n) 实现——无论如何都是 O(log n) 算术运算；整个事情的时间复杂度取决于您正在使用的任意大型算术库的时间复杂度。