Sorteringsalgoritm med tidskomplexitet O(n + k log(k))
Hej har fått följande uppgift och kört lite fast:
Designa en algoritm som som sorterar n stycken heltal där det förekommer dubbletter. Det totala antalet olika tal är k. Beskriv algoritmen i pseudokod.
Din algoritm ska ha tidskomplexitet O(n + k log(k)). Förväntad tid räcker. För vilka värden på k blir algoritmen linjär?
Hur ska jag göra? Jag har kollat igenom tråden här:
https://cs.stackexchange.com/questions/108454/is-there-a-sorting-algorithm-of-order-n-k-logkTacksam för svar.
Men vet inte riktigt hur jag ska implementera proceduren som pseudokod. Tacksam för svar.
Proceduren som signaturen ryan visar på StackExchange är redan skriven i pseudokod. Pseudokod är ett informellt sätt att beskriva en procedur eller algoritm så du kan skriva den (nästan) hur du vill. När jag skriver pseudokod blir det ofta något som liknar programmeringsspråket Python.
Det jag tänkte var att man skulle skriva pseudokoden mer i kodformat, exempelvis så att det liknar Python eller Java. Jag har skrivit så här:
- Spara siffrorna i en vektor. Skapa därefter en hashtabell med nycklar som siffrorna i vektorn, och siffrornas frekvens som korresponderande data. Tidskomplexiteten för insättning av enskild element till en hashtabell är O(1), men eftersom det i detta fall finns n distinkta element som loopas igenom i vektorn, förblir tidskomplexiteten för denna procedur O(n).
- Sortera alla nycklar i hashtabellen med en sorteringsalgoritm med tidskomplexiteten O(k log(k)). Denna kan exempelvis vara quicksort (som har O(k log(k)) som medelfall) eller mergesort.
- Radera de ursprungliga elementen i vektorn och lägg därefter till de sorterade siffrorna antalet gånger som dess frekvens. Radering och insättning av element i en vektor tar konstant tid, O(1) medan tidskomplexiteten för att slå upp ett element i en hashtabell är linjär, O(1).
Men skulle vilja att det mer såg ut som en kod.
Om man ska tro signaturen ryan och några till på StackExchange så är det inte möjligt att åstadkomma en komplexitet lägre än O(n log k).
The short answer is no, in the worst-case comparison based algorithms, for reasons stated here.
De verkar vara väldigt kunniga men det vore kul om du kunde motbevisa dem genom att presentera en algoritm som är O(n + k log k).
ryan har ett förslag till en variant av Quicksort som med komplexitet O(n log k). Det presenteras i en form av pseudokod som enkelt kan skrivas som Python. Han ger också en analys av algoritmen för den som vill dyka djupare i komplexitetens ocean.
