循环中多次数组访问的Big O复杂度分析疑问

首先直接给出结论：你提到的3*O(1)=O(3)=O(1)这个分析思路完全正确。

核心逻辑 #

Big O表示法的本质是描述算法复杂度随输入规模增长的渐近趋势，它会忽略所有常数系数和低阶项。不管是1次、3次还是任意固定次数的O(1)操作，它们的总时间复杂度依然是O(1)——因为固定次数的常数操作不会随着输入规模（比如数组长度）的增大而变化。

结合代码示例说明 #

看你给出的递归代码：

Loop(Index i)
{
  if A[i] > 5
  {
    count++;
    if A[i+1] > 5
      Loop(i+1)
    if A[i+2] > 5
      Loop(i+2)
  }
}

单次调用Loop函数时，确实会执行3次数组访问：A[i]、A[i+1]、A[i+2]，每一次都是O(1)。这三次操作的总时间复杂度就是O(1)，完全符合你之前的推导。

不过要额外注意：这里说的是单次函数调用的数组访问复杂度。如果看整个递归流程的总时间复杂度，那就是另一回事了——因为递归会触发多次Loop调用，次数取决于数组中大于5的元素分布，最坏情况下可能达到指数级，但这和你问的“多次O(1)操作的复杂度合并”是两个独立的问题。

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