Bonjour, 

je souhaite connaître la complexité dans le pire des cas de l'algorithme suivant, qui crée une liste de N entiers distincts tirés aléatoirement. 

Je pense que c'est O(N), mais je ne suis pas sûr. Merci beaucoup !

entrée: N
sortie: un tableau de N entiers distincts parmi {1, ..., N}

T un tableau vide de taille N
repeter pour i de 0 à N-1
    k = entier choisi au hasard
    tant que k est deja present dans T
        k = entier choisi au hasard
    T[i] = k

C'est pas vraiment une question sur la programmation en C...

Il faut sans doute ajouter une hypothèse : le choix au hasard se fait parmi les nombres de 1 à N.

• Dans le pire des cas, on n'a pas de chance, et ça ne termine pas.
• Dans le meilleur des cas, O(n)
• La complexité moyenne est un exercice intéressant, mais trop compliqué pour moi :-)

-
Edité par michelbillaud 16 août 2018 à 10:20:51

Je n'ai pas trouvé de topic "Algorithmique" 

Merci beaucoup pour ta réponse!

En fait on pourrait rapprocher cet algo du problème du collectionneur où une personne veut compléter une collection de N objets, sachant qu'elle trouve les objets en achetant des céréales (le tirage au hasard) et on se demande combien d'objets elle doit acheter pour compléter sa collection (avoir tiré tous les éléments de 1 à N). Le résultat est qu'en moyenne il lui faudra acheter N ln(N) boîtes de céréales.

Mais ça ne te donne pas ta complexité car ceci ne prend pas en compte les opérations pour vérifier qu'un objet (qu'un entier) n'a pas encore été obtenu (tiré au hasard dans le tableau).

PS : Mais vu que tu veux tirer N nombres entre 1 et N, tu obtiens forcément tous les nombres entre 1 et N et donc ton algo peut se faire en temps constant, on renvoie le tableau des entiers de 1 à N. Si tu voulais tirer k nombres entre 1 et N avec k < N), ce que tu pourrais également faire, c'est mélanger ton tableau et prendre les k premiers éléments.

EDIT : @michelbillaud, dans le meilleur des cas, ce n'est pas du O(N), vu qu'il faut quand même prendre le temps de vérifier que le nombre tiré n'a pas encore été tiré, et on a donc la somme des entiers de 1 à N - 1, donc du O(N^2).

-
Edité par yo@n97one 16 août 2018 à 20:42:42

Exact,  je me suis planté. J' avais en tête la question du nombre (min,  max, moyen) de tirages a effectuer. Ce n' est pas le nombre d' opérations élémentaires.

Faut toujours penser à bien lire l' énoncé.

Enfin bon pour le max c' est pareil : complexite "infinie" puisque quelque soit le nombre  X aussi grand qu' on veut,  il existe des scénarios où X étapes ne sont pas suffisantes.

Par contre, il existe des algos linéaires et faciles pour construire une permutation dans un tableau. Ce qui est sans doute la question d'après 🦄

Et je n'ai pas répondu à la complexité moyenne, mais si en moyenne on fait N ln(N) tours de la boucle externe, j'ai envie de dire que la complexité moyenne de l'algo est en O((Nln N)^2). À vue de nez.

Pour la complexité en moyenne :

Quand on a déjà rempli  K cases, la probabilité de tirer une des N-K valeurs non encore utilisées (parmi N), pour la mettre dans la case K+1 doit être  (N-K)/N.   Et le nombre moyen de tirages à  faire pour y arriver doit être l'inverse N/(N-K).

Ce qui nous donne la somme  N( 1/N + 1/(N-1) + 1/(N-2) + ... 1/2 + 1) =   N. H(N)     

Coucou la série harmonique ! https://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique

(en espérant ne pas raconter trop de conneries !)

-
Edité par michelbillaud 17 août 2018 à 17:51:41

Oui c'est le résultat du problème du collectionneur (avec H(n) équivalent à ln(n) en plus l'infini). Mais ça ne donne que le nombre moyen de tirages, puisque ça ne prend pas en compte la vérification que le nombre n'a pas encore été tiré.

-
Edité par yo@n97one 17 août 2018 à 18:07:16

yo@n97one a écrit:

Oui c'est le résultat du problème du collectionneur (avec H(n) équivalent à ln(n) en plus l'infini). Mais ça ne donne que le nombre moyen de tirages, puisque ça ne prend pas en compte la vérification que le nombre n'a pas encore été tiré.

-
Edité par yo@n97one il y a 3 minutes

Ah, je savais bien que j'oubliais un truc.

Chaque verification au niveau K coute K+1 etapes. On est parti pour

N. ( 1/N + 2/(N-1) + 3/(N-2) + .....   N/1)