Quicksort, nombre d'operations

[Jeanthon]

Bonjour,

Je débute en algorithmique et je bute sur un exercice :

Soit une liste non ordonnée de taille N.
Dans Quicksort, on choisit le pivot de telle sorte que la liste se divise a chaque fois en deux liste de taille g.N et (1-g)N.
Alors, le temps nécessaire pour trier une liste est : T(g)=T(g.N) + T[(1-g)N] + N

Question : montrer que T(N)=A(g).N.ln(N) et determiner la constante A(g). Comment A(g) se comporte lorsque a est proche de 0 ou 1?

Je vous explique un peu pourquoi je bloque :

Dans un autre cas ou on prend N une puissance de 2, et le pivot divisant en deux parties egales, pas de probleme puisqu'a chaque fois la liste se divise "proprement", et au final on obtient N listes de 1 element. Je connais T(1) donc je peux calculer la suite T(N).
En revanche, ici N et g sont quelconques. Donc on obtient des sous listes dont le nombre d'element n'est pas entier. Comment palier à ce probleme? Alors mettons que je m'arrange pour qu'a chaque division, j'arrondi les nombres d'element de sorte a retrouver des nombres entiers. Je rencontre un deuxieme problème : Comment faire le calcul analytiquement?

J'ai d abord construit un petit logarithme sur mon pc, qui me sort le nombre d’opération T(N), et en fitant je trouve bien une loi en N.ln(N). Mais mon prof m'affirme que je dois m'en sortit analytiquement. Et la je bloque completement, je ne vois pas comment aborder cette suite.

Merci de votre aide
-----

[Jeanthon]

Je precise que l'exercice est tiré du livre "Nature of Computation", exercice 3.11

[ProgVal]

Bonjour,

Les tailles des sous-listes ne sont surement pas celles que tu annonces, puisque g est un entier, c'est donc totalement incohérent (la première sous-liste aurait plus d'éléments et la second en aurait un nom négatif).
En revanche, g et N-g paraissent beaucoup plus crédibles.

De plus, le membre de gauche de la relation de récurrence doit être T(N) et non T(g).

Ce qui nous donne donc : T(N) = T(g) + T(N-g) + N

Valentin

[Jeanthon]

T(N) oui pardon.

Mais le reste est correct. Je n'ai pas dis que g devais être un entier. Ici je pense que c'est un réel compris entre 0 et 1. De cette manière c'est cohérent. Voici le lien pour l'exo :

Page 78, Exercice 3.11 "Partway to the median"
http://books.google.it/books?id=z4zM...epage&q&f=true

Si tu sais comment m'y prendre pour rectifier mon premier message...

[A voir en vidéo sur Futura]

[Jeanthon]

Je viens de discuter avec mon prof, il suffit de verifier que la solution fonctionne...... Donc tout devient plus simple d'un seul coup!

[Jeanthon]

Le problème c'est donc considérablement simplifié Je trouve A(g) = 1/[-g.ln(g)-(1-g).ln(1-g)]

Je remarque que A(g) est l'inverse de l'entropie d'un processus de Bernoulli. Mais bon de la à faire un lien..... Vous voyez un truc intelligent à remarquer?