Föreläsning 7

Question 1

Vilka påståenden är sanna?

• Ingen annan algoritm för sortering med jämförelser klarar sig med färre jämförelser än mergesort, oavsett hur indata ser ut.
• I en binär heap med N element går det att hitta en given nyckel på O(log N) tid.
• Mergesort är en optimal algoritm för sortering med jämförelser.
• En binär heap kan användas för att sortera N element på O(N log N) tid.
• En binär heap kan implementeras som en enda array, och tar därför mindre plats än ett binärt sökträd som innehåller samma element.
• Det är omöjligt att sortera N element på mindre än ~ N lg N tid i värsta fall.

Answer 1

• Mergesort är en optimal algoritm för sortering med jämförelser.
• En binär heap kan användas för att sortera N element på O(N log N) tid.
• En binär heap kan implementeras som en enda array, och tar därför mindre plats än ett binärt sökträd som innehåller samma element.