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

Κ17.7 · Αναζήτηση αριθμημένης θέσης σε αίθουσα

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

Ψάχνω αν η αριθμημένη θέση μου J-13 υπάρχει (κάποιες λείπουν) στην αίθουσα προβολής N×N θέσεων. Χρειάζομαι τόσα βήματα:

• O(n²)
• O(log n)
• O(2ⁿ)
• 0 - μετά τον κόβιντ δεν έχει βγει ταινία της προκοπής

Συχνή παρανόηση

Το 33% επέλεξε O(n²), σαν να έπρεπε να ελέγξει κάθε θέση μία-μία. Επειδή όμως οι θέσεις είναι ταξινομημένες, δεν χρειάζεται να τις κοιτάξετε όλες.

Υπόδειξη

Οι θέσεις είναι αριθμημένες με σειρά (γραμμή και αριθμός)· σκεφτείτε ποιον αλγόριθμο αναζήτησης σας επιτρέπει αυτή η διάταξη.

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