algorithm - 带条件的循环的运行时间(步数)

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 循环只是在等待进程完成，所以不考虑运行时间的计算。第一个内部 while 循环将 i 向右移动，直到它被卡住。第二个内部 while 循环将 k 向左移动，直到它卡住。

线条

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

将 i 和 k 移动到它们被卡住的点上方。

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