1
svar
90
visningar
Samsorteringsalgorithm för listor - varför är varje körning O(n)?
Hej!
Har en fråga om facit i nedanstående uppgift
Facit:
Jag har markerat frågan jag har genom att stryka under den relevanta delen i facit. Hur kan vi vara så säker på att listan sorteras i $O(n)$ tid? Generellt brukar väl inte sorteringsalgorithmer för listor vara så bra som $O(n)$...?
Som jag tolkar frågan, så är de stycken listorna redan sorterade (var för sig) från början. Man ska inte sortera varje lista.
Man ska "bara" slå ihop (merge) dessa listor så att man får en lång sorterad lista med element.
Edit: Ursprungligen hade jag för mig att varje lista innehåller element, men det är totalt element i alla listor ihop enligt uppgiftens frågeställning
