ΠΛΗ30 - ΜΑΘΗΜΑ 2.1 - ΔΙΑΙΡΕΙ & ΒΑΣΙΛΕΥΕ - ΘΕΩΡΙΑ ΜΕΡΟΣ 3/3 (STRASSEN)

1) Διαίρει και Βασίλευε
1.1) Ο αλγόριθμος MergeSort (Ταξινόμηση με Συγχώνευση)
1.2) Ο αλγόριθμος QuickSort (Γρήγορη Ταξινόμηση)
1.3) Ο αλγόριθμος QuickSelect (Γρήγορη Επιλογή)
1.4) Ο αλγόριθμος Strassen για τον πολλαπλασιασμό πινάκων
Ασκήσεις

[apostolislocalgreece]

Στον ψευδοκώδικα που παραθέτεται για τον πολλαπλασιασμό δισδιάστατων πινάκων ΑxB=C βλέπουμε οτι για κάθε πολ/σμό που γίνεται μεταξύ των στοιχείων γραμμής i του Α και και των αντίστοιχων στοιχείων της στήλης j του Β έχουμε μία πρόσθεση άρα για κάθε στοιχείο του C γίνονται 2n πράξεις. Αλλά αυτό έχει να κάνει με τον τρόπο που τρέχει ο συγκεκριμένος αλγόριθμος .Αν το κάνει κάποιος με "χαρτί και μολύβι" βγαίνει οτι για κάθε στοιχείο του πίνακα C έχουμε n πολ/σμους και n-1 προσθέσεις. Σωστά;
Το ρωτάω αυτό γιατί στις εφαρμογές παίρνουμε σαν δεδομένο οτι για κάθε στοιχείο του nxn C πίνακα "αποτελέσματος" έχουμε 2n πράξεις που όμως δεν ισχύει γενικά ("χαρτί μολύβι") αλλά το δεχόμαστε χάριν απλότητος ...και γιατί έτσι κι αλλοιώς το Θ βγαίνει το ίδιο. Σωστά;