昨天Fibonacci 数列算法GC++执行。有数据，有真相，开源码QQH ：）

http://bbs.wenxuecity.com/znjy/4639264.html

complexity。一个很好的例子就是 Fibonacci sequence 的计算。

f(n) = f(n-1) + f(n-2)

f(0) = 0

f(1) = 1

直接 top-down 用 recursion 计算会产生 exponential time complexity。得要 bottom-up 往上堆积才会产生 linear time complexity。

http://bbs.wenxuecity.com/znjy/4639289.html

没想到的是这个数列增长的非常快。第93项，F93是64位整数可以装下的最大的，F94就OVERFLOW了。除非用啥特殊大整数包裹，标准的C++ 最多能计算到93项。别提百万项了，和和。

这是现有的标准的Fibonacci 数列数据头2000项：

https://oeis.org/A000045/b000045.txt

F93=12200160415121876738

F2000=

4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141
5110884460875389096036076401947116435960292719833125987373262535558026069915859152294924539049987
2225679531698287448247299226390183371677806060701161549788671987985831146887087626459736908672288
4023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717
881930324025204312082516817125

 

F93 用两种算法法的执行时间差不多。

FIBLOOP Run time: 0.062832

FIB Recursive with Save and Lookup Run time: 0.065826

------跑的结果 ------

FIBLOOP

F0: 0
F1: 1
 N: 93
 F2: 1
 F3: 2
 F4: 3
 F5: 5
 F6: 8
 F7: 13
 F8: 21
 F9: 34
 F10: 55
 F11: 89
 F12: 144
 F13: 233
 F14: 377
 F15: 610
 F16: 987
 F17: 1597
 F18: 2584
 F19: 4181
 F20: 6765
 F21: 10946
 F22: 17711
 F23: 28657
 F24: 46368
 F25: 75025
 F26: 121393
 F27: 196418
 F28: 317811
 F29: 514229
 F30: 832040
 F31: 1346269
 F32: 2178309
 F33: 3524578
 F34: 5702887
 F35: 9227465
 F36: 14930352
 F37: 24157817
 F38: 39088169
 F39: 63245986
 F40: 102334155
 F41: 165580141
 F42: 267914296
 F43: 433494437
 F44: 701408733
 F45: 1134903170
 F46: 1836311903
 F47: 2971215073
 F48: 4807526976
 F49: 7778742049
 F50: 12586269025
 F51: 20365011074
 F52: 32951280099
 F53: 53316291173
 F54: 86267571272
 F55: 139583862445
 F56: 225851433717
 F57: 365435296162
 F58: 591286729879
 F59: 956722026041
 F60: 1548008755920
 F61: 2504730781961
 F62: 4052739537881
 F63: 6557470319842
 F64: 10610209857723
 F65: 17167680177565
 F66: 27777890035288
 F67: 44945570212853
 F68: 72723460248141
 F69: 117669030460994
 F70: 190392490709135
 F71: 308061521170129
 F72: 498454011879264
 F73: 806515533049393
 F74: 1304969544928657
 F75: 2111485077978050
 F76: 3416454622906707
 F77: 5527939700884757
 F78: 8944394323791464
 F79: 14472334024676221
 F80: 23416728348467685
 F81: 37889062373143906
 F82: 61305790721611591
 F83: 99194853094755497
 F84: 160500643816367088
 F85: 259695496911122585
 F86: 420196140727489673
 F87: 679891637638612258
 F88: 1100087778366101931
 F89: 1779979416004714189
 F90: 2880067194370816120
 F91: 4660046610375530309
 F92: 7540113804746346429
 F93: 12200160415121876738
Run time: 0.062832
FIB Recursive

 F1: 1
 F0: 0
 F2: 1
 F1: 1
 F3: 2
 F4: 3
 F5: 5
 F6: 8
 F7: 13
 F8: 21
 F9: 34
 F10: 55
 F11: 89
 F12: 144
 F13: 233
 F14: 377
 F15: 610
 F16: 987
 F17: 1597
 F18: 2584
 F19: 4181
 F20: 6765
 F21: 10946
 F22: 17711
 F23: 28657
 F24: 46368
 F25: 75025
 F26: 121393
 F27: 196418
 F28: 317811
 F29: 514229
 F30: 832040
 F31: 1346269
 F32: 2178309
 F33: 3524578
 F34: 5702887
 F35: 9227465
 F36: 14930352
 F37: 24157817
 F38: 39088169
 F39: 63245986
 F40: 102334155
 F41: 165580141
 F42: 267914296
 F43: 433494437
 F44: 701408733
 F45: 1134903170
 F46: 1836311903
 F47: 2971215073
 F48: 4807526976
 F49: 7778742049
 F50: 12586269025
 F51: 20365011074
 F52: 32951280099
 F53: 53316291173
 F54: 86267571272
 F55: 139583862445
 F56: 225851433717
 F57: 365435296162
 F58: 591286729879
 F59: 956722026041
 F60: 1548008755920
 F61: 2504730781961
 F62: 4052739537881
 F63: 6557470319842
 F64: 10610209857723
 F65: 17167680177565
 F66: 27777890035288
 F67: 44945570212853
 F68: 72723460248141
 F69: 117669030460994
 F70: 190392490709135
 F71: 308061521170129
 F72: 498454011879264
 F73: 806515533049393
 F74: 1304969544928657
 F75: 2111485077978050
 F76: 3416454622906707
 F77: 5527939700884757
 F78: 8944394323791464
 F79: 14472334024676221
 F80: 23416728348467685
 F81: 37889062373143906
 F82: 61305790721611591
 F83: 99194853094755497
 F84: 160500643816367088
 F85: 259695496911122585
 F86: 420196140727489673
 F87: 679891637638612258
 F88: 1100087778366101931
 F89: 1779979416004714189
 F90: 2880067194370816120
 F91: 4660046610375530309
 F92: 7540113804746346429
 F93: 12200160415121876738
Run time: 0.065826

 UINT64_MAX=18446744073709551615

 

所有跟帖： 

• 体会到的是Recursive 算法是有可能通过记忆和利用中间结果大大砍掉重复的迭代树支call，形成接近线性路经大大提高速度 -网恋无罪- ♂ (0 bytes) () 06/13/2019 postreply 21:01:24

• 真执着，呵呵 -amigo- ♂ (539 bytes) () 06/14/2019 postreply 05:56:24