exemple de complexité en moyenne

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 :oops:

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 :whistle:

Citation:

---

Envoyé par Franck Dernoncourt

Si f est une fonction constante, ça simplifie les choses ;)

---

malheureusement:calim2:, f dépend de n

Citation:

---

Envoyé par prgasp77

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 :)

---

Euh par contre, si je me plante pas, la complexité en moyenne est O(n) et pas O(1) ;)

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 :

Code:

---

1 2 3 4

Je marque le nœud courant comme visité Je choisi un nœud non visité relié au nœud courant Je m'y rends Si c'est A, fini, sinon goto 1

---

En moyenne, il faut 7/3 déplacements et proportionnellement autant d'instructions pour arriver à A, soit un algo de complexité moyenne O(1).
Dans le pire des cas, il faut n+1 déplacements ... algo en O(n) donc.

Cdlt,

encore plus simple :

Code:

---

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 :aie: !

Bonjour,

je vous remercie pour l’intérêt que vous portez à mon sujet, en fait j'ai du mal :mur:à comprendre comment calculer la complexité en moyenne, si on modifie un peu l'exemple de Mr Franck comme suit:

Code:

---

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)

---

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 :merci:

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

Citation:

---

Envoyé par bazoga

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.

---

La plupart des opérations sur une hashtable.

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.

Citation:

---

Envoyé par Franck Dernoncourt

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.

---

L'énoncé parle de complexité moyenne (= amortie). Il y a beaucoup de structures de données qui proposent des opérations en complexité amortie constante. Un simple tableau dynamique par exemple.

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