找到小于给定数字的斐波那契和小于O（n）

Question

我想解决一个问题，部分解决方案是找到小于输入数字的finbonacci数字的总和。现在输入数字的上限是10 ** 9。我已经将问题简化为以下O（n）解决方案，我想知道是否有更高效的解决方案。

b=[1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 
10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 
1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 
39088168, 63245985, 102334154, 165580140, 267914295, 433494436, 701408732, 1134903169, 1836311902] 

def test_lambda(a): 
    list_numbers= filter(lambda x: x<=a, b) 
    return len(list_numbers) 

正如你可以看到我与给定的输入比较表b的值并返回一个小于给定数量的元素。

b为fibonaccis数高达该索引的总和的列表，因此第一数目为1时，总和为1时，第二是1的总和是2时，第三2之和4 ...

Answer 1

您可以（使用bisect_right函数实例）为只需使用二进制搜索：

from bisect import bisect_right 

def test_lambda(a): 
    return bisect_right(list_numbers,a) 

或者，如果你想小于输入数量的总和，你可以使用：

from bisect import bisect_right 

def less_than(a): 
    return a[bisect_right(list_numbers,a)-1] 

这是可行的，因为列表是预先计算的并且严格递增。这意味着它是一个有序列表。二进制搜索在O（log n）中有效，因此可以高效地进行搜索。另外我想补充0到列表（在第一位置），因此，有0查询，输入被解析，以及：

from bisect import bisect_right 

b=[0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 
    4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 
    514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 
    24157816, 39088168, 63245985, 102334154, 165580140, 267914295, 433494436, 
    701408732, 1134903169, 1836311902 
    ] 

def less_than(a): 
    return a[bisect_right(list_numbers,a)-1] 

Answer 2

这可以在O完成（LOGN）* O（LOGN）利用矩阵幂请参考以下链接
https://math.stackexchange.com/questions/1102452/modulus-of-sum-of-sequence-of-fibonacci-numbers
柜面你没有足够的内存来存储所有10^9个和，如果你想小于总和你可以使用这个O（LOGN）来计算第i总和，等于给定的输入，你可以只是二进制搜索我