Discussion :

[mohamed sarr]

Bonjour j'ai essayé de déterminer la complexité de cette algorithme mais j'ai trouvé tetha(n) je veux que vous me le vérifiez merci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Procédure Maxmin1(S, n : in; max, min : out)
début
    min   S[1];
    max   S[1];
    i   1;
    tant que i < n faire
        i   i + 1;
 
        si S[i] > max alors
            max   S[i]
        Fin si
        si S[i] < min alors
            min   S[i]
        Fin si
    Fin tant que
Fin

Quelle est sa complexité exacte en nombre de comparaisons?

[iakou]

Bonjour.

Cette fonction retourne le minimum et le maximum d'une suite 'S' de longueur 'n'.
Elle exécute n-1 itérations et (n-1)*2 comparaisons.

Le code me rappelle ce que j'ai étudié dans les années 80 en IUT à LILLE. (de l'algo influencé par PL1, c'est uniquement pour cela, que je réponds)
En revanche je ne peux rien vous dire sur 'theta()' et la complexité, car à l'époque cela n'était pas au programme.

Bonne continuation dans vos études.