время работы алгоритмов

Question

В этом алгоритме

int j=1; 
while (j<=n/2) { 
    int i=1; 
    while (i <= j) { 
     cout << j << " "<< i << endl; 
     i++; 
    } 
    cout << endl; 
    j++; 
} 

бы время работы этого алгоритма будет Т (п) = (п^2/2) + п + 4

for (int i=2; i <=n; i++) { 
    for (int j=0; j <= n;) { 
     cout << i << " "<< j << endl; 
     j=j+(n/4); 
    } 
    cout << endl; 
} 

Было бы T (n) = (n-2)^2 + 2

Answer 1

для первого. T (n) = сумма чисел от 1 до n/2, потому что внешний цикл вводится n/2 раза, и для тех n/2 раз внутренний цикл будет вводиться 1 раз и первый поворот, 2 раза и 2-й поворот , 3 раза на 3-м повороте ...

T (n) = ((n/2)/2) * ((n/2) +1) = n/4 * (n/2 + 1) = n/4 * ((n + 2)/2)

Возможно, вы можете упростить его, выполнив умножение.

Второй. T (n) = (n + 1) * (n/4), потому что внешний цикл будет вводить n + 1 раз, и для каждого из этих периодов внутренний цикл будет вводить n/4 раза.

Т (п) = (п + 1) * (п/4)

Answer 2

В одном 2-й, приращение петли пропорциональна конечной точке контура. Число итераций не увеличивается с n, а только диапазон значений. Начиная с j=0, он принимает не более 5 приращений j+=(n/4) для j <= n, чтобы стать ложным. (Только 4, если n кратно 4). В любом случае это O (1).

Таким образом, внутренняя петля 2-й версии выполняет ~ 5 операций, а снаружи цикла находится cout << endl, поэтому каждая итерация внешнего цикла выполняет ~ 6 операций печати. (Если они подключены к терминалу, это будет только строка-буферизация, поэтому подсчет стоимости по количеству напечатанных строк = количество системных вызовов. Если это будет файл, по умолчанию он будет заблокирован по блоку, поэтому стоимость ~ = количество операций ~ = число 4k блоков данных, напечатанных.)

Внешний цикл 2-й версии работает от i = 2 .. n, поэтому он запускается n-1 раз, каждый раз печатая 6 строк. (или 5, если n%4 == 0). T (loop2) = 6n.

Анализ Хассана выглядит нормально для первого цикла.