这段代码的含义是什么？

Question

我正在为考试做准备,我正在做一些考试 - 我提出了一个问题,我有点不确定.

题:

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

我也认为B必须是正确的答案,因为如果A [i] == 0,forloop中的if语句会比较.最坏的情况是N.

我不确定的是,你何时称之为"阵列访问",何时进行比较？这就是为什么我不确定,如果答案是B或A.

Answer 1

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

答案不能是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次.