Quelle est la complexité de cet algorithme?

Question

J'apprends à trouver la complexité de l'algorithme et je ne peux pas comprendre quelle est la complexité de cet algorithme. Quelqu'un pourrait-il m'expliquer comment obtenir la réponse?

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;
    }
}

Veuillez toute contribution est la bienvenue. Voici ce que j'ai jusqu'à présent:

Answer 1

La complexité est (a ^ 2 / b)

Comme je l'ai décrit dans l'image, vous devez résumer tous les "x", alors vous obtiendrez la complexité.

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

Donc à la fin, si "a" et "b" étaient pour le même ordre alors le résultat est:

O (c) = 0 (c est numérique)

cela signifie que la complexité est dans l'ordre numérique. mais si "a" était pour l'ordre supérieur alors le résultat est:

O ((a ^ 2) / b)

Answer 2

Tel que amodifié, vous devriez l'avoir dans les paramètres de la somme:

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

si a = k * b, la boucle externe effectue des itérations k. Par conséquent, la complexité finale est:

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

Comme vous l'avez mentionné

, la complexité du temps l'est

.