帶條件的循環的運行時間（步數）

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訪問了其他數組元素，但數組中的每個元素只被訪問一次。