Complexité d'algorithme

[Mekkadra]

Salut les gars
S'il vous plaît quelqu'un qui connaît la complexité me conseiller dans la résolution de cet exercice

question:donner la complexité de l'algorithme suivant:



*****************************************
*- quotient de la division de 'n' par 'm' et le reste 'r' : *
*****************************************

*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
*/* */*
*/* Algorithme division(m,n,q,r:entier); */*
*/* Debut */*
*/* q:=0; */*
*/* r:=0; */*
*/* Tantque m<=r faire */*
*/* q:=q+1; */*
*/* r:=r-m; */*
*/* finfaire; */*
*/* FIN. */*
*/* */*
*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*

Je sais que la solution est: O(n/m).


Merci d'avance :++:

[Carpate]

Salut les gars
S'il vous plaît quelqu'un qui connaît la complexité me conseiller dans la résolution de cet exercice

question:donner la complexité de l'algorithme suivant:



*****************************************
*- quotient de la division de 'n' par 'm' et le reste 'r' : *
*****************************************

*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
*/* */*
*/* Algorithme division(m,n,q,r:entier); */*
*/* Debut */*
*/* q:=0; */*
*/* r:=0; */*
*/* Tantque m<=r faire */*
*/* q:=q+1; */*
*/* r:=r-m; */*
*/* finfaire; */*
*/* FIN. */*
*/* */*
*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*

Je sais que la solution est: O(n/m).


Merci d'avance :++:

C'est bizarre m n'est pas initialisé et n'évolue pas dans la boucle tant que ...

[Pythales]

[quote="Mekkadra"]Salut les gars
S'il vous plaît quelqu'un qui connaît la complexité me conseiller dans la résolution de cet exercice

question:donner la complexité de l'algorithme suivant:



*****************************************
*- quotient de la division de 'n' par 'm' et le reste 'r' : *
*****************************************

*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
*/* */*
*/* Algorithme division(m,n,q,r:entier); */*
*/* Debut */*
*/* q:=0; */*
*/* r:=0; */*
*/* Tantque m=m faire
n:=n-m;
q:=q+1;
r:=n;
fin faire

Par contre, je ne sais pas comment on mesure la complexité d'un algorithme.

[LeJeu]

Bonsoir
@Mekkadra : on ne comprend pas bien tous tes */*...
en plus propre tu peux nous donner

Code: Tout sélectionner

[COLOR=Blue]*/* quotient de la division de 'n' par 'm' et le reste 'r' [/COLOR]

[B]Algorithme division(m,n,q,r:entier)[/B]
Debut
    q:=0;
    r:=0;
    Tantque m<=r faire
        q:=q+1;
        r:=r-m;
    finfaire;
FIN.

C'est tout pareil mais plus facile à lire ...
et comme le voit bien Carpate ça ne marche pas,
il faut initialiser r

Code: Tout sélectionner

[B]Algorithme division(m,n,q,r:entier)[/B]
Debut
    q:=0;
    r:=[COLOR=Red]n[/COLOR];
    Tantque m<=r faire
        q:=q+1;
        r:=r-m;
    finfaire;
FIN.


sinon la complexité, c'est grosso modo le nombre de calcul, donc de tour de boucles de cet algo...

On soustrait donc à n le nombre m tant que c'est possible
par exemple
n = 20
m = 7
donne comme reste 20 13 6

et ce donc environ n/m fois ... ( on n'est pas à 1 près..)