Comment prouver le nombre le plus défavorable d'inversions dans un tas est Ω (nlogn)?

Je suis occupé à préparer les examens, à faire quelques vieux examens. La question ci-dessous est la seule que je n'arrive pas à faire (je ne sais pas trop par où commencer). Toute aide serait grandement appréciée. Utilisez la limite de tri de comparaison Ω (nlogn), la limite thêta (n) pour la construction de segments ascendante et la complexité d'ordre du tri d'insertion pour montrer que le nombre d'inversions dans le tas le plus défavorable est Ω (nlogn).Comment prouver le nombre le plus défavorable d'inversions dans un tas est Ω (nlogn)?

Source

2010-06-09 htdIO

"et la complexité de la commande si le tri par insertion" - quoi? – sth

C'est tout ce qu'ils vous donnent. J'ai copié/collé la question. Mais si je me souviens bien, le type d'insertion en tas est O (n^2)? – htdIO

Comment un tas peut-il avoir des inversions? La définition d'un tas empêche les éléments d'être verticalement hors service. Voulez-vous dire des inversions dans un tableau sous-jacent sur lequel le tas est mappé, ou quelque chose? –

La complexité du tri par insertion est O (n + d) où d est le nombre de paires d'inversion. Maintenant, disons que vous aviez un ensemble de nombres que vous heapifiez (Theta (n)), puis effectuez le tri d'insertion sur eux. Que dit-il à propos du nombre le plus défavorable de paires d'inversion dans le tableau de tas?

Source

2010-06-09 16:40:34

Je pense que c'est la question: que dit-elle? :) – IVlad

@ | Vlad: Ai-je vraiment besoin de l'épeler? Le smiley me fait penser que vous plaisantez, mais aucun upvote ne me fait penser que vous êtes sérieux ;-) :-P –

@Moron - personnellement je l'ai compris, mais je pense que plus de détails seraient bien pour l'OP. Comme quoi «Omega» et «Theta» signifient et comment ils vous aident à arriver au résultat. – IVlad

Comment prouver le nombre le plus défavorable d'inversions dans un tas est Ω (nlogn)?

Répondre

Questions connexes