请解释这段Java代码的时间复杂度（Big-O）及计算方法

先看代码核心逻辑：这是一个递归函数，当index <= 0时直接返回数组第一个元素（属于O(1)的常数操作）；否则会递归调用自身三次，分别传入index-1、index-2、index-4，最后做几次常数时间的比较返回结果。

具体计算方法 #

1. 定义复杂度函数：设T(n)为输入index = n时，函数执行的总操作数（代表时间复杂度）。
2. 写出递推关系式：
   • 当n <= 0时，T(n) = O(1)，因为只做一次数组访问和返回操作。
   • 当n > 0时，函数会触发三个递归调用，加上后续的比较判断（都是常数时间），所以递推式为：

     T(n) = T(n-1) + T(n-2) + T(n-4) + O(1)
     

3. 分析递推式的增长速度：
   这个递推式的增长比斐波那契数列的递推式（T(n)=T(n-1)+T(n-2)）更快，因为多了一个T(n-4)的调用项。我们可以通过特征方程求解它的渐近增长：
   • 递推式对应的特征方程为：r⁴ - r³ - r² - 1 = 0
   • 求解该方程，最大的实根约为α ≈ 1.754877666，这是决定复杂度增长速度的主导项。
4. 确定Big-O复杂度：
   忽略常数项和低阶项后，这段代码的时间复杂度为O(1.755ⁿ)，属于指数级复杂度——每次递归调用都会分裂出三个子调用，且子问题的规模递减幅度不大，导致整体操作数呈指数级爆炸增长。

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