循环中的大O型阵列访问

Question

我知道数组访问是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)
}
}

我知道这段代码并不完整、多余、永无止境，但我只是想了解Big O和数组访问的逻辑。这个循环有3个数组访问，每个访问位于O(1(。所以3*O(1(=O(3(=O。这个想法正确吗？

Answer 1

是；单个阵列访问的时间复杂度是恒定的，即使在其附近还有其他阵列。3是一个常数，因此总体复杂性不会增加。如果您改为使用n阵列访问，则时间复杂性将变为O(n)。