循环内嵌套二分查找的时间复杂度分析及序列匹配代码咨询

让我们一步步拆解这段Java代码的时间复杂度，先从核心细节入手：

基础组件的复杂度 #

你用到的indexOf()是二分查找实现，它的时间复杂度是 O(log m)——这里的m是输入数组arr的长度。二分查找每次将搜索范围减半，对数级的复杂度是确定的。

循环执行次数的关键观察 #

你的目标递推序列 Aₙ = Aₙ₋₁ + 2*Aₙ₋₂（初始项A₀=1、A₁=3）是指数级增长的：

• 解这个线性递推式可以得到，它的主导增长项是2ⁿ（负根的影响会被快速抵消）。简单来说，序列值会爆炸式增长：A₁₀=1027，A₂₀超过100万，A₃₀达到1亿级别，哪怕是Javalong类型能容纳的最大值，也只需要不到60次迭代就会超出。
• 这意味着代码里的while循环执行次数t是一个极小的常数——完全不会随数组长度m变化，不管数组多大，循环最多只会跑几十次。

总的时间复杂度 #

代码里所有的耗时操作都是常数次的二分查找：

• 初始阶段对A₀、A₁的两次查找（或者更少，如果提前返回的话）
• 循环内的常数次查找
  由于大O表示法会忽略常数系数，常数次的O(log m)操作叠加后，总的时间复杂度仍然是 O(log m)。

额外补充几个边界情况的复杂度：

• 如果数组里不存在A₀（即1），代码直接返回-1，只执行1次二分查找，复杂度还是O(log m)
• 如果只存在A₀，返回0，同样只执行1次二分查找

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