Prouver ou réfuter: Il existe un algorithme de tri général qui peut trier un tableau de longueur n dans O (n) s'il est min-heap-ordonné

Question

Démontrer ou réfuter: Il existe un algorithme de tri général qui peut trier un tableau de longueur n dans O(n) si le tableau est min-heap-ordonné.

Demain, j'écris examen et très peur de travail de preuve ... Voici que je trouve de plus et examen très difficile pour les résoudre comme prévu ...:/

Je pense que je sais, mais mon réponse la raison n'est pas bonne. Donc, ma raison est que l'instruction est fausse parce que quand array est min-heap-ordered, imaginons-le comme un arbre, alors les feuilles de l'arbre ne seront pas triées. Et ce tableau est trié est nécessaire pour le trier en O(n). Pour cette raison déclaration est erronée ..

Ici, j'ai exemple, je fais mon propre arbre commandé min tas:

 1 
    /\ 
    3 2 
    /\ \ 
    8 99 7 

A partir de ce que nous faisons ensemble, nous avons 1, 3, 2, 8, 99, 7 Vous voyez, ce n'est triée à tout sauf min-tas-ordonné. Impossible de trier ceci dans O(n).

---

Très sûr que mes résoudre est mal pls pouvez-vous me montrer comment vous le faites correctement et désolé pour mon anglais, je fais de mon mieux ..

Je pense que mes résoudre est mademoiselle, je dois prouver ce min-tas-ordonné n'a pas de feuilles triées? Mais comment?

Answer 1

Cette solution est parfaitement correcte. Vous pouvez produire une preuve formelle reductio ad absurdum (réduction à une contradiction) en utilisant l'algorithme de tri hypothétique pour produire un algorithme de tri général linéaire.

L'algorithme en temps linéaire pour trier le tableau A consiste à construire un réseau ordonné tas en commençant par une séquence ordonnée d'entiers inférieurs à min(A), puis en ajoutant A à la fin.La longueur totale de ce nouveau tableau est O(|A|) - avec la représentation de tableau standard d'un tas, vous avez besoin de la prochaine puissance plus grande de 2 éléments, qui est au maximum 3·|A|. Vous pouvez ensuite utiliser l'algorithme linéaire pour trier un tableau ordonné en tas pour trier ce nouveau tableau, et enfin supprimer la séquence ajoutée pour produire le tableau original dans l'ordre trié. Puisque cela contredit le résultat bien connu que le tri général linéaire est impossible, nous pouvons conclure qu'il n'existe pas d'algorithme linéaire pour trier un tableau ordonné en tas.

Answer 2

La preuve habituelle pour ce genre de problèmes est de réduire un problème bien connu à la vôtre. Autrement dit, vous montrez que s'il est possible de résoudre votre problème en temps linéaire, il est également possible de résoudre un problème X en temps linéaire. Mais on sait que X n'est pas résoluble en temps linéaire, donc par contradiction votre problème n'est pas aussi bien.

Un excellent exemple d'un tel problème X est le tri. Il est bien connu qu'il est impossible de trier N éléments en Omega(n log n) temps (Omega est ici une bonne façon de traiter les limites inférieures, voir here).

noter maintenant que si nous:

1. faire un min tas d'éléments N
2. tri N éléments de commande min tas

nous trions efficacement ces éléments à partir de zéro. Ainsi, l'une ou l'autre de ces deux étapes prend au moins n log n temps. Il existe un algorithme pour effectuer la première étape en temps linéaire (il devrait probablement être dans votre manuel), en nous donnant la limite inférieure Omega(n log n) pour la deuxième étape, Q.E.D.