这种算法分析是否正确？

Question

假设有一个整数向量，从位置 -infinite..2..1..0..1..2..+infinite 开始。
只有一个位置会包含整数值1，其他位置会包含0，算法会找到包含整数值1的位置。

考虑"verifyDoor" 方法 O(1).

我已经有了这个解决方案，我想知道我的分析是否正确。

我得出以下结果：
T(n)=8n+10
T(n)=O(n)

这里是：

代码：

int findDoor(int[] wall){
    if(verifyDoor(0)){              // 1
        return 0;                   // 1
    }

    int p =1;                       // 1
    while(1){                       // n
        if(verifyDoor(p)){          // n+1
            return p;               // n+1
        }else{                      // n+1
            if(p>0){                // n+1
                p=p*-1;             // n+1
            }else{                  // n+1
                p=(p*-1)+1;         // n+1
            }
        }
    }
}

考虑"n"向量长度
T(n) = 8n+10（这将是每条指令的总次数运行）
T(n) = O(n)

Answer 1

是的，它是 O(n)，但是将它算作 8n + 10 通常没有多大意义，因为某些操作比另一个操作需要更多的时间，而您甚至不知道它。

例如}else{并不总是需要额外的时间，因为有些编译器只是实现了"goTo"，不管它是跳转到"else"分支还是在if分支之后...

或者声明变量比赋值要多花费 100 个计时器等等

Answer 2

O(n)？什么是n？你需要定义 n.

如果n是门到位置0的距离，那么复杂度是O(n)。

这是因为，对于位置i的一扇门，算法对[-|i|,|i|]中的每个位置都访问一次（除了-i如果i为正），而且只有2|我|或 2|i| + 1 个这样的位置。每次访问需要 O(1) 时间。

这种算法分析是否正确？

Is this analysis of algorithm correct?

algorithm

big-o

code-analysis

asymptotic-complexity