有关Binet公式的内容

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

使用Binet的公式为O（1），标准的迭代实现为O（n）。

但是让我们谈谈第n个斐波纳契数的计算方法……这就是问题：即使这是一个标准的面试问题，但如果没有更多信息，这实际上是没有意义的。这是一个不好的问题，也就是说，除非被告知我们要忽略标准编程语言整数和浮点数的有限性。斐波那契数呈指数增长。只要没有选择朴素的递归实现，它们就会在选择特定算法之前就溢出标准编程语言类型。

这里要具体说明，这是在C＃中返回第n个斐波那契数的两种实现。顶级的实现了Binet的双精度封闭形式解决方案，并将其转换为长整数，在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个斐波那契，在非人为情况下，它的值应为O（1），这不是因为Binet的公式，而是因为您应该使用其中包含92个项目的查找表。在C ++中，您可以使用constexpr函数在编译时生成92个项目。

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