欧拉计划第2题（偶数斐波那契数）：能否用O(1)时间复杂度求解？

斐波那契数列的每一项由前两项相加生成。以1和2为起始项，前10项为：1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
求斐波那契数列中不超过400万的所有偶数项之和。

问题：是否可以用O(1)（常数时间）复杂度求解该问题？ #

答案：完全可以 #

首先观察原斐波那契数列的奇偶性规律：

• 数列的奇偶性以3为周期循环：奇、偶、奇，每3项出现一个偶数项。
• 这些偶数项本身构成一个独立的线性递推数列：设 ( E_k ) 为第k个偶数项，则 ( E_k = 4 \times E_{k-1} + E_{k-2} )，起始项为 ( E_1=2 )，( E_2=8 )。

基于这个递推关系，我们可以推导其通项公式（通过解特征方程）：
[ E_k = \frac{(2+\sqrt{5})^k - (2-\sqrt{5})^k}{\sqrt{5}} ]

接下来只需完成两步固定计算：

1. 通过通项公式定位最大的k：计算可知 ( E_{11}=3524578 )（小于400万），下一项 ( E_{12}=14930352 )（超过400万），因此有效项为 ( E_1 ) 到 ( E_{11} )。
2. 用递推关系推导求和公式：累加整理后可得，前n个偶数项的和 ( S_n = \frac{E_{n+2} - E_2}{4} )。代入n=11并计算 ( E_{13} )，即可直接得到最终结果。

整个过程无需循环遍历，所有操作都是固定步骤的算术运算，因此属于O(1)常数时间复杂度。

内容的提问来源于stack exchange，提问作者Haziq