找到小於給定數字的斐波那契和小於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總和，等於給定的輸入，你可以只是二進制搜索我