Discussion :

[Hayato]

Bonjour,
J'ai une hésitation concernant la complexité d'une boucle dont ne sait pas quand elle s'arrêtera bien que probablement elle n'est pas infinie même si théoriquement rien ne l'interdit...

Produire au hasard valeur entre 1 et 10
Tant que valeur > 5
Produire au hasard valeur entre 1 et 10
Fin tant que


Quelle serait la complexité de la boucle tant que puisqu'à priori rien n'interdit à la boucle d'être infinie même si en pratique ce n'est sans doute jamais le cas.
Merci pour d'éventuels éclaircissements.

[KiLVaiDeN]

je dirais ( 1 / n² )
Mais j'ai ptet tort...

[sjrd]

Sachant que la complexité est calculée dans le pire des cas, il est évident qu'ici elle est en O(infini)

[Matthieu Brucher]

C'est quoi n ?
D'un point de vue algorithmique, on en peut pas borner son temps d'exécution. D'un point de vue statistique, on peu donner une borne sup du temps d'exécution à x%.

[KiLVaiDeN]

1) je suis nul en math
2) je me suis dit que la chance que la condition soit vraie était divisée par 2 à chaque répétition de la boucle, d'où mon (1/n²) qui apparement était une ânerie ( bâtée )

Promis je relierais des cours de complexité d'algorithmes...

[Jedai]

On peut calculer la complexité en moyenne, et ici elle est très visiblement :
somme( n/2^n, n = 1 à +inf ) qui converge absolument.

--
Jedaï

[KiLVaiDeN]

Quelqu'un aurait un lien sur le net pour se mettre à jour dans le domaine des calculs de complexité d'algorithmes ?

[FrancisSourd]

Lorsqu'on a affaire à des algorithmes randomisés, on s'intéresse souvent à l'espérance du temps de calcul. On peut soit en calculer une estimation, soit en donner une borne supérieure.

En général, l'estimation se fait en fonction de la taille des données fournies en entrée. Dans ton algo, il n'y a pas d'entrée, il est difficile d'exprimer une complexité en fonction de cette entrée. En revanche, on peut facile estimer l'espérance du nombre d'itérations de la boucle: c'est la loi de Poisson. Oups, je corrige, ce n'est pas la loi de Poisson mais bien la somme de la série n/2^n, comme dit ci-dessus! Cela donne 2.

[Nemerle]

Sachant que la complexité est calculée dans le pire des cas, il est évident qu'ici elle est en O(infini)

No, car la génération aléatoire n'est que pseudo. Il faut voir quel est le cycle du générateur considéré.

De plus, il n'y a pas de complexité à calculer dans cette algo qui ne dépend pas de paramêtres.... (statique vs dynamique)

[DrTopos]

Le mot 'complexité' m'a l'air tout à fait inapproprié ici. Il me semble que la seule chose qu'on puisse mesurer dans le cas de l'exemple est la probabilité d'arrêt après n tirages et encore en supposant, d'abord que les 10 valeurs sont équiprobables (système non biaisés) et deuxièmement que les tirages sont indépendant les uns des autres. Dans ce cas la probabilité d'arrêt après le n-ieme tirage est de 1 - (1/2^n).

[Matthieu Brucher]

Pas mieux

[Hayato]

Merci, j'ai trouvé une solution dans un bouquin, il s'agit bien de calculer l'espèrance pour un algo randomisé :o

[random]

il y a ici une limite absolue
c'est la mémoire disponible
pour représenter le nombre obtenu .5^n jai besoin d'un système de notation
ce nombre dépend du système de numération utilisé
quand j'aurais saturé ma mémoire et mon disque je ne pourrais plus calculer la proba suivante faute de pouvoir la discrimer dans mon système
de notation
faute de proba dénombrable, je ne puis rien faire sauf racheter de la mémoire

[Jedai]

Random : Il n'y a pas de limite dû au matériel (à part son vieillissement), son algorithme est en mémoire constante.

--
Jedaï