Bonsoir,
je cherche un exemple d'algorithme dont la complexité en moyenne est O(1) et dans le cas le pire O(f(n)). // peut importe la fonction f.
aidez moi svp
Cordialement
E.Bazoga
Bonsoir,
je cherche un exemple d'algorithme dont la complexité en moyenne est O(1) et dans le cas le pire O(f(n)). // peut importe la fonction f.
aidez moi svp
Cordialement
E.Bazoga
Salut, je l'apprends (presque) en même temps que toi : http://fr.wikipedia.org/wiki/Tri_par_paquets
L'idée est pas conne
Si f est une fonction constante, ça simplifie les choses
Mouarf ! détournement de sujet ! Police !
vite fait, bien fait
Exact ... quel boulet. Alors j'en ai un, mais il est tordu.
Imaginons un graphe « étoilé » : il y a un nœud A auquel n nœuds Bi sont reliés ; de plus, chaque Bi est relié à b(i-1) et B(i+1) (B1 étant relié à B2 et Bn).
On cherche à aller du nœud B1 au nœud A en suivant cet algorithme :
En moyenne, il faut 7/3 déplacements et proportionnellement autant d'instructions pour arriver à A, soit un algo de complexité moyenne O(1).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 Je marque le nud courant comme visité Je choisi un nud non visité relié au nud courant Je m'y rends Si c'est A, fini, sinon goto 1
Dans le pire des cas, il faut n+1 déplacements ... algo en O(n) donc.
Cdlt,
encore plus simple :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 Dummy(x) // x est un tableau on va dire A := rand(0, length(x)) // retourne une valeur aléatoire entre 0 (inclus) et length(x) If A == 0 browse all x's items return
J'ai pas compris ... parcourir tous les éléments de A ... quels éléments ?
Désolé, je voulais dire parcourir tous éléments de x
Dans ce cas, c'est sûrement un '=' à la place du '<', car tel quel, l'ago est en moyenne comme dans le pire des cas en O(n)
ah oui encore désolé, wow il faut que j'arrête de poster lorsque je me lève !
Bonjour,
je vous remercie pour l’intérêt que vous portez à mon sujet, en fait j'ai du mal à comprendre comment calculer la complexité en moyenne, si on modifie un peu l'exemple de Mr Franck comme suit:
est ce qu'on peut dire que cette algorithme a pour complexité en temps moyenne O(1) et en pire des cas O(nlog(n)) "cout du trie" ? si oui, une petite démonstration sera la bienvenue
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 Dummy(t) // t est un tableau on va dire A := rand(0, length(t)) If A == 0 trie_par_tas(t)
Cordialement
Bazoga
Je conseille de lire le chapitre 5 intitulé "Probabilistic Analysis and Randomized Analysis" du livre de référence http://algo.developpez.com/livres/#L2100039229
Oui, tu devrais plutôt t'intéresser aux exemples donnés par pseudocode ... va savoir pourquoi ça ne nous ait pas passé à l'esprit.
Ce genre d'énoncé sans grand intérêt, cela donne envie de répondre par un cas tordu, non ?
En outre, l'algo que je donne permet de généraliser facilement pour tout f.
Je parle également de complexité moyenne. Une autre façon de tordre les résultats est de poser des hypothèses sur la distribution des entrées données à l'algorithme.
Sinon, si intéressé, un algo de tri O(1) (non utilisable en pratique, et son worst case est également O(1) donc ça ne répond pas à l'énoncé) que j'aime beaucoup : http://www.scribd.com/doc/55808256/2...ting-Algorithm
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager