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

Κ15.6 · Πολυπλοκότητα μέτρησης ψηφίων

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

Μετράω τα ψηφία οποιουδήποτε αριθμού n μου δοθεί. Η χρονική πολυπλοκότητα του αλγορίθμου μου είναι:

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

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

Το 45% επέλεξε O(n), μπερδεύοντας την τιμή του n με το μέγεθος της εισόδου: ο αλγόριθμος κάνει μία επανάληψη ανά ψηφίο, όχι ανά μονάδα της τιμής.

Υπόδειξη

Πόσες φορές μπορείτε να διαιρέσετε το n με το 10 πριν φτάσει στο 0; Συγκρίνετε το πλήθος των ψηφίων του 1000 και του 1000000.

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