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

Κ15.8 · Πολυπλοκότητα O(n² + log n)

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

Ένας αλγόριθμος μπορεί να έχει πολυπλοκότητα O(n² + log n).

• True
• False

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

Το 60% απάντησε False, θεωρώντας ότι το O(·) πρέπει να περιέχει έναν μόνο όρο· η έκφραση είναι σωστή, απλώς ισοδυναμεί με O(n²), γιατί ο κυρίαρχος όρος είναι το n².

Υπόδειξη

Το O(·) περιγράφει ένα άνω φράγμα με μια συνάρτηση· σκεφτείτε αν είναι λάθος να γράψουμε μια συνάρτηση που δεν έχει απλοποιηθεί, και σε τι απλοποιείται αυτή.

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