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

Κ15.5 · Πολυπλοκότητα μέτρησης bit

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

Μια συνάρτηση παίρνει έναν αριθμό n και επιστρέφει πόσα bit είναι 1. Πόσο γρήγορη μπορώ να κάνω αυτήν τη συνάρτηση;

• O(n³)
• O(n²)
• O(n)
• O(f(x))
• O(log n)

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

Το 32% επέλεξε O(n), μπερδεύοντας την τιμή του n με το πλήθος των bit του, που είναι περίπου \(\log_2 n\).

Υπόδειξη

Πόσα bit χρειάζονται για να γράψετε τον αριθμό n στο δυαδικό;

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