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

Κ15.4 · Πολυπλοκότητα πολλαπλασιασμού πινάκων

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

Μια συνάρτηση πολλαπλασιάζει δύο πίνακες m1, m2 διαστάσεων N × N (με τον συνήθη αλγόριθμο, γραμμή επί στήλη). Η χρονική πολυπλοκότητά της είναι:

O(n²)
O(n!)
O(n)
O(τρέχα γύρευε)
O(log n)
O(n³)

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

Το 23% επέλεξε O(n²), μετρώντας μόνο τα N² στοιχεία του αποτελέσματος και όχι το εσωτερικό άθροισμα N γινομένων για το καθένα.

Υπόδειξη

Μετρήστε πόσα στοιχεία έχει ο πίνακας-αποτέλεσμα και πόσους πολλαπλασιασμούς χρειάζεται ο υπολογισμός του καθενός.

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