Dus de ruimte-efficiëntie van QuickSort is O (log (n)). Dit is de ruimte die nodig is om de oproepstack te behouden.
Nu, volgens de wikipedia-pagina op quicksort , komt dit in aanmerking als een in-place-algoritme, omdat het algoritme is gewoon elementen in de ingangsgegevensstructuur ruilen.
volgens deze pagina De ruimte-efficiëntie van O (log n) diskwalificeert Disqualifies Quicksort om op zijn plaats te zijn , omdat de ruimte-efficiëntie groter is dan O (1). Volgens deze definitie is elk algoritme met ruimte-efficiëntie groter dan O (1) niet in de plaats. Dus ik neem aan dat dit betekent dat alle recursieve algoritmen per definitie niet op zijn plaats zijn?
Het is duidelijk dat er hier twee verschillende definities van in-place zijn. Wikipedia is niet altijd een geheel betrouwbare bron, dus ik heb een van mijn hoogleraren geraadpleegd.
Mijn professor was het met de tweede definitie overeengekomen. Hij zei dat Quicksort niet in de plaats zit. Ook al blijven de gegevens in de ingangsarray, de extra ruimte die nodig is voor de stapel diskwalificeert het. Mijn professor schreef een populair boek over algoritmen, dus respecteer ik zijn mening enorm, maar dit antwoord lijkt me gewoon niet correct.
Ik zie het eigendom van in de plaats als behoorlijk letterlijk. De gegevens blijven op zijn plaats. Het verplaatst zich niet van zijn oorspronkelijke gegevensstructuur. Voor mij is deze definitie nuttiger, omdat het betekent dat u uw algoritme met pointers kunt uitvoeren in plaats van u te vragen gegevens te kopiëren. Dit lijkt een waardevol eigendom van een algoritme en waardig van de naam “in-place”.
Antwoord 1, Autoriteit 100%
Inleiding tot algoritmenvan MIT Press kwalificeert QuickSort als in-place– het sorteert de elementen binnen de array met maximaaleen constant aantal ervan buiten de array op een bepaald moment.
Uiteindelijk zullen mensen altijd verschillende meningen hebben (wordt memoriseren van bovenaf beschouwd als dynamisch programmeren? Niet voor sommige ‘klassieke’ mensen), de kant van wie je het meest vertrouwt. Ik vertrouw de redacteuren en de auteurs van MIT Press (samen met mijn professor, die het als in-place kwalificeert).
Het probleem met QuickSort is meestal niet dat het niet ter plaatse sorteert, maar dat het niet stabielis – satellietgegevens worden niet op volgorde gehouden.
Bewerken
Kuroi’s punt benadrukt een deel van dit argument dat volgens mij erg belangrijk is.
Velen beweren dat het O(log(n)) extra geheugen nodig heeft voor recursieve aanroepen en dat de gegevens gelekt worden in de vorm van de indices op de stapel, maar dit is verwaarloosbaar voor zeer grote maten van N (log(1.000.000.000) =~ 30) en negeert het feit dat het verplaatsen van gegevens op de heap doorgaans veel, veel langer duurt, wanneer size(data) >> maat(index).
De indices van de gegevens zijn niet de elementen zelf – dus de elementen van de gegevens worden niet buiten de array opgeslagen, behalve een constant aantal ervan (in elke aanroep).
Antwoord 2, autoriteit 32%
Strikt genomen heeft Quicksort een ruimte-efficiëntie van O(n) aangezien het gedegenereerde geval een index op de stapel zou vereisen voor elk element van de array. Hoewel het gemiddeld O(log(n)) zal zijn. Gezien het feit dat ik denk dat er geen enkele manier is om het een “in place” -algoritme te noemen, tenzij je een gedegenereerde definitie van “in place” gebruikt, wat betekent dat de originele gegevens niet buiten de oorspronkelijke arraygrenzen worden opgeslagen (exclusief kopieer/swap-bewerkingen).
Deze definitie van “op zijn plaats” zou gedegenereerd zijn omdat u een “buiten de plaats” algoritme zou kunnen nemen en het aan deze “op zijn plaats” -vereiste kunt voldoen door het al zijn extra gegevensopslag te laten gebruiken aan de oorspronkelijke array . Wanneer het antwoord wordt gevonden, kunt u de originele array “op zijn plaats” opnieuw rangschikken met behulp van de aanwijzergegevens.
Antwoord 3, Autoriteit 14%
QSORT doet inderdaad de gegevens op zijn plaats, maar de stapelruimte die wordt gebruikt voor recursie is in log 2 (n).
Deze twee eigenschappen zijn niet tegenstrijdig. Meestal “op zijn plaats” verwijst naar heapgeheugen, d.w.z. wat u moet expliciet toewijzen voor het algoritme om te werken.
Een logaritmische ruimtecomplexiteit is echter in principe verwaarloosbaar, behalve in pathologische gevallen (zeggen dat u een quicksort wilt doen op een 8 bits microcontroller met 512 bytes van stapel :)).
Antwoord 4, Autoriteit 5%
Het hangt allemaal af van de definitie van “in-place” algoritme.
Als u “in-place” definieert als een constante hoeveelheid geheugen vereist, is QuickSort niet “in-place”, omdat het log (n) geheugen voor de recursie vereist.
Als u “In-Place” definieert als mensvriendelijker “beweegt de gegevens niet buiten de ingangsstructuur”, dan is QuickSort opnieuw niet “in-place”. De gegevens lekken in het geheugen in de vorm van indices waarmee de QuickSort-methode wordt aangeroepen, die nodig zijn voor algoritme om te werken. De inhoud van dit extra geheugen direct is afhankelijk van op de ingang, hoe het niet lekt?
Als u “in-place” als niet-kopiëren definieert, hoe zit het dan met een stom algoritme om een som van een array te vinden: maak een andere reeks lengte (N – 1) met elementen zoals B [I] = A [ I + 1] + A [0] / n. Dit is een beetje kopiëren, hoewel de inhoud anders is, maar de inhoud van dit extra geheugen is een functie van de invoergegevens, net als de indices die op stapel in QuickSort-algoritme worden gehouden.
Ik denk dat de wikipedia-definitie van “in-place” het nuttigst is, en volgens deze is de quicksort niet “in-place” omdat het een niet-constante hoeveelheid geheugen gebruikt.