Qual è la complessità di questo algoritmo?

Question

Sto imparando a trovare la complessità dell'algoritmo e non riesco a capire qual è la complessità di questo algoritmo. Qualcuno potrebbe spiegarmi come ottenere la risposta?

void algorithm(int a, int b) {
    while (a >= b) {
        int x = a - b;
        for (int i = 0; i <= x; i++) {
            std::cout << "complexity of this algorithm?";
        }
        a = x;
    }
}

Per favore, qualsiasi input è il benvenuto. Questo è quello che ho finora:

Answer 1

La complessità è (a ^ 2 / b)

Come ho descritto nell'immagine, devi sommare tutte le "x", quindi otterrai la complessità.

in summation part for (-b -2b -3b - ... -nb) you can write :
[![enter image description here][1]][1]-b (1+2+...)
so this is -b*(n(n+1)/2)

summation_part_definition_link

Quindi, alla fine, se "a" e "b" fossero per lo stesso ordine, il risultato è:

O (c) = 0 (c è numerico)

questo significa che la complessità è in ordine numerico. ma se "a" era per l'ordine superiore, il risultato è:

O ((a ^ 2) / b)

Answer 2

Come aviene modificato, dovresti averlo nei parametri della somma:

(1) x = a - b  // first iteration
(2) x = a - 2b // second iteration
(3) x = a - 3b
...

se a = k * b, il ciclo esterno itera kvolte. Quindi, la complessità finale è:

(a - b) + (a - 2b) + ... + (a - (k-1) b) = 
(k-1) b + (k-2) b + ... + b = k * (k-1) * b/2

Come hai detto

, la complessità del tempo è

.