第 n 个斐波那契的线性算法中的离群值

Question

所以我被教导使用斐波那契数的递归关系，我可以得到一个 O(n) 算法。但是，由于大 n 的斐波那契数的大尺寸，加法所需的时间成比例地更长：这意味着，时间复杂度不再是线性的。

一切都很好，但是在这张图中 (source)，为什么 1800000 附近的数字比它的邻居需要更长的计算时间？

编辑：如答案中所述，离群值约为 180000，而不是 1800000

Answer 1

probably the measurement of time was done on a system where other tasks were performed simultaneously, which was causing a single computation to take longer than expected.

OP 未复制的部分图表说：

Note: Each data point was averaged over 10 calculcations[sic].

所以这似乎否定了这种解释，除非它是 巨大的 差异，我们只看到它与正常时间的平均值。

(我的 2012 vintage Mac mini 使用作者的代码在 1/2 秒内计算出第 200,000 个数字。生成此数据的机器用了 4 秒来计算第 200,000 个数字。我拉出一本 2009 年份的 Mac 书来确认这是可信的。）

我用代码的修改版本做了自己的粗略图表，每次都没有在开始时重新启动，但总共保持了运行时间，并得出了以下图表：

时间比预期的要长一些，因为我使用的算法在每次计算中增加了一些打印开销。但是18万到19.5万之间没有大的异常。

Answer 2

异常值出现在 180,000，而不是 1,800,000。我不知道 python 中存储了多大的整数，但假设 32 位字存储为二进制，fib(180000) 需要接近 100,000 个字节。我怀疑测试为什么 180,000 会比 181,000 或 179,000 花费更长的时间。

@cdlane 提到了从 fib(170000) 到 fib(200000) 需要的时间，但是增量是 1000，所以这将是 30 个测试用例，每个运行 10 次，这将需要不到 20 分钟。

链接到的文章提到了用于计算斐波那契数的矩阵变体，它是一个 log2(n) 过程。这可以使用类似逻辑的卢卡斯序列进一步优化（重复平方以提高矩阵的幂）。 64 位无符号整数的示例 C 代码：

uint64_t fibl(uint64_t n) {
    uint64_t a, b, p, q, qq, aq;
    a = q = 1;
    b = p = 0;
    while(1) {
        if(n & 1) {
            aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
        }
        n >>= 1;
        if(n == 0)
            break;
        qq = q*q;
        q = 2*p*q + qq;
        p = p*p + qq;
    }
    return b;
}

第 n 个斐波那契的线性算法中的离群值

Outlier in linear algorithm for nth Fibonacci

performance

fibonacci