Confused о временной сложности вложенных циклов и ищет советы

Question

Допустим, у меня есть два кода:

Код A:

for i = 0; 
for j = 0; 
while(i<n){  // O(n) 
    while(j<n){ // O(n) 
     printf("hello"); 
     ..... 

Время работы = о (п) х О (п) = O (N^2) ..

Код B:

int result = 0; 
int i = 0; 
while (i < n/2){ //O(n) 
result += arr[i]; 
i += 1; 
    while(i >= n/2 && i < n){ //O(n) 
     results += arr[i]; 
     i +=1; 
     } 

Ru nning time = O (n)

Как сделать код B, мы НЕ МНОЖЕМ МНОЖЕСТВО O (n), чтобы получить O (n^2), как мы это делали для кода A? Очень путают, как определить время работы.

Answer 1

Дадим пробег кода B в нашей голове:

Предположим, что n достаточно велико, скажем, по крайней мере 100. Первоначально мы имеем i = 0, поэтому условие для внешней петли true, i будет потом увеличение на 1 по линии 5 (i += 1). Итак, на данный момент мы имеем i = 1, однако в этом случае условие внутреннего цикла равно false, поэтому мы просто продолжаем следующий поворот внешнего цикла.

Условия для внешнего контура и внутренней петли остается true и false соответственно, пока i не станет n/2 - 1, на данном этапе, условие внешнего цикла является true, и так i увеличивается до n /2, и в этом случае условие для внутреннего цикла равно true. Таким образом, i будет увеличен до n внутренним циклом.

Наконец, у нас есть i = n, условия для петель равны false, и он не будет двигаться дальше.

Так сложность приводится ниже:

i   Work done 
------------------------ 
0   1 
1   1 
2   1 
.   . 
.   . 
.   . 
n/2-2  1 
n/2-1  n/2 + 1 

Так общая работа является:

(1 + n/2 - 2) * 1 + 1 * (n/2 + 1) = O(n)