Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Κ17.5 · Μέση πολυπλοκότητα της quicksort

Kahoot «Δυαδική Αναζήτηση και Ταξινόμηση» (διάλεξη 17) · Δυσκολία ★★☆ · multiple-choice · 66% σωστές απαντήσεις (71 απαντήσεις στο αμφιθέατρο) · Κεφάλαια: 17, 18

Η χρονική πολυπλοκότητα στη μέση περίπτωση (average case) της quicksort είναι:

• O(n²)
• O(n log n)
• O(n)
• O(1)

Υπόδειξη

Σκεφτείτε πόσα επίπεδα διαμέρισης έχει η quicksort όταν ο pivot χωρίζει τον πίνακα περίπου στη μέση, και πόση δουλειά γίνεται σε κάθε επίπεδο.

Αριθμός στον οδηγό: Κ17.5 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: kahoot-quicksort-average · Σύνδεσμος: https://progintro.github.io/study/questions/kahoot/kahoot-quicksort-average.html · Markdown (GitHub)