运行有条件循环的时间（步数）

Question

我不确定如何根据输入大小 N 确定运行时间，尤其是当它进入具有某些限制的循环时。这就是我尝试过的。我猜常数是正确的。它看起来如何？

i = 1;                                //1
k = n;                                //1
while (i <= k) {                      //N+1
    while (i <= k && A[i] < 0) {      //i+2   
        i = i + 1;                    //2i
    }
    while (i <= k && A[k] >= 0) {     //i+2
        k = k - 1;                    //2i
    }
    printf("...");                    //1
    i = i + 1;                        //1
    k = k - 1;                        //1
}

Answer 1

这就是所谓的蜡烛两端燃烧。 i 和 k 将在中间某处相遇，但数组中的每个元素都只访问一次。所以运行时间是 O(n).

外部 while 循环只是在等待进程完成，因此不会影响运行ning 时间的计算。第一个内部 while 循环将 i 向右移动，直到它被卡住。第二个内部 while 循环将 k 向左移动，直到它卡住。

行

i = i + 1;
k = k - 1;

将 i 和 k 移动到他们卡住的位置。

结果是i访问了部分数组元素，k访问了其他数组元素，但每个数组元素只访问一次。

运行有条件循环的时间（步数）

Run time (number of steps) of loops with conditions

algorithm

performance

big-o

运行 有条件循环的时间（步数）

Run time (number of steps) of loops with conditions

algorithm

performance

big-o

运行有条件循环的时间（步数）