en place rapide de tri de a O(n) ou O(logn) de l'espace de la complexité

Ce Wikipidea article http://en.wikipedia.org/wiki/Quicksort#In-place_version suggère que O(logn) est l'espace-temps de la complexité pour en place de tri et de http://futur3googl3r.blogspot.com/2008/08/google-interview-questions.html cette interview du site l'indique, il est O(n). Je pense que la réponse est O(n) mais je voulais savoir si je suis en droit.

Deux d'entre eux probablement décrire le même algorithme (je n'ai pas lu dans les détails). O(n) espace pire de cas, et O(log n) espace moyenne.

OriginalL'auteur vkaul11 | 2013-02-22

  1. 11

    Dans ces deux articles, l'espace d'une complexité, qui se réfère à l'est de la supplémentaire de l'espace (sans compter l'espace nécessaire pour stocker le tableau d'origine). Cette supplémentaire espace peut venir de la pile d'appel, en plus de la commune cas où un supplément de tableau est déclaré. Chaque appel récursif permettra de créer un cadre de pile sur la pile d'appel, qui prend de la place, et le nombre de frame de pile dépend de la taille de l'image n, il doit donc être compté.

    Nous permettent d'utiliser l'article de Wikipédia pour la référence, puisque le blog est tout à fait incohérent comme l'a souligné @Jim Mischel.

    En cours de tri rapide, la modification de l'implémentation naïve donnera O(log n) supplémentaire espace en moyenne, au lieu de la O(n) supplémentaire de l'espace (dans tous les cas) dans l'implémentation naïve. Le pire des cas complexité de supplémentaire de l'espace, comme l'a souligné correctement par le blog1, est O(n), lorsque l'algorithme rencontre son pire des cas (une liste triée; il y aura n appels récursifs de sorte que la pile d'appel prendra O(n) supplémentaire de l'espace).

    1: (Merci à @rici pour souligner) Cependant, le blogueur n'est exacte que si l'on suppose une mise en œuvre sans l'optimisation tel que mentionné dans le Article de Wikipedia. Il est possible d'améliorer l'algorithme à utiliser O(log n) supplémentaire de l'espace dans le pire des cas, par recursing sur la plus petite partie de la première et de la mise en œuvre d'une queue d'appel pour la partie plus longue. Depuis la plus petite partie est toujours inférieure à la moitié de la taille de saisie, il y aura au plus O(log n) appels récursifs. En supposant que la queue d'appel d'optimisation est effectuée, la partie plus longue de réutilisation de l'actuel cadre de pile sans encourir des espaces supplémentaires. Si la queue-appel d'optimisation n'est pas fait, on peut toujours écrire un processus itératif de mise en œuvre explicite de la pile.

    Pire des cas, la complexité est O(n) mais H2CO3 donne O(logn) comme le pire des cas, la complexité sans en donner la raison.
    Le premier paragraphe de ce blog est contradictoire. Il souligne à juste titre que le pire des cas est O(log n) appels récursifs, mais alors continue à dire qu'il peut faire en O(n) imbriqués les appels récursifs. Qui est-ce? Et le deuxième paragraphe est tellement hors du champ gauche, que c'est incompréhensible.
    Le blog semble être tout à fait incohérent sur le pire des cas, la complexité de l'espace supplémentaire de en place rapide de tri. Pire des cas est O(n), et la moyenne des cas est O(log n).
    Écrit quicksort pour prendre le pire des cas en O(log n) l'espace est l'exercice 7-4 dans mon exemplaire de Cormen &al, qui est, de l'omi, une meilleure référence de hasard blogueur qui n'est manifestement pas le concept de la queue-de récursivité.
    L'essentiel est que si vous avez toujours recurse d'abord sur la plus courte de la partition, puis le nombre de imbriquée appels récursifs est o(log n) parce que la plus courte partition est inférieure à la moitié de la taille totale de la partition. La queue de la récursivité n'est pas un imbriquée appel, de sorte que le blogueur est mal (et je ne crois pas qu'il est un googleurs, soit).

    OriginalL'auteur nhahtdh

  2. 1

    Cette interview suggère que c'est O(n)

    Non, ce n'est pas le cas:

    Solution: Quicksort a un espace complexité de O(logn), même dans le pire des cas.

    Il dépend de la mise en œuvre de l'algorithme. Comme l'article de wikipédia explique il y a deux implémentations, vous pouvez faire de la simple mise en œuvre avec O(n) de l'espace et de la meilleure mise en œuvre qui utilise seulement O(logn) de l'espace
    Lire l'intégralité de la solution "La version de quicksort en place de partitionnement utilise uniquement la constante de l'espace supplémentaire avant tout appel récursif. Toutefois, si elle a fait en O(logn) imbriqués les appels récursifs, il a besoin de stocker une quantité constante de l'information de chacun d'eux. Depuis le meilleur des cas, fait au plus O(logn) imbriqués les appels récursifs, il utilise O(logn) de l'espace. Le pire des cas fait O(n) imbriqués les appels récursifs, et doit donc O(n) de l'espace". Voir dans le lien que j'ai posté futur3googl3r.blogspot.com/2008/08/...
    L'article dit aussi: "lors de la mise en œuvre avec précaution" 🙂
    J' a lire l'article.
    H2CO3, vous pouvez au moins expliquer pourquoi le pire des cas, la complexité n'est pas O(n) mais en O(logn) au lieu de dire que c'est ainsi.

    OriginalL'auteur