algorithm - 这段代码的哪个陈述是正确的？

Question

我正在为我的考试做准备，我正在为此做一些练习 - 我遇到了一个问题，我有点不确定。

问题:

我确定答案不可能是 C 或 D，因为代码的最佳运行时间是 O(1)，最坏情况下的运行时间是 O(n)。

我还认为 B 一定是正确答案，因为 forloop 中的 if 语句会比较 A[i] == 0。最坏的情况是 N。

我不确定的是，您什么时候称某些东西为“数组访问”，什么时候是比较？这就是为什么我不确定答案是 B 还是 A。

Answer 1

答案是 B - 在最坏的情况下，这段代码总共进行了 2N 次比较。假设循环是空的。运行空循环需要 N 次比较(i < n)。现在考虑 if循环内的语句 - 在最坏的情况下，这是另外 N 次比较，总共 2N 次比较。

答案不能是 C，因为在“最佳情况”下，我们发现数组的第一个元素为 0，并且循环在仅进行 2 次比较后返回，使最佳情况 O(1) 保持不变。

答案显然不是D；这个循环没有二次方。它显然是线性的。

答案不可能是A，因为在最坏的情况下我们只访问数组N次。这发生在 s[i] ，就在与 0 进行比较之前。

考虑以下等效代码:

int n = s.length();
for (int i=0; i < n; i++)
{
    int v = s[i];
    if (v == 0)
        return i;
}

现在应该更清楚什么是比较，什么是数组访问。在最坏的情况下，我们将访问数组 N 次。