Ο ΑΛΓΟΡΙΘΜΟΣ 22#22

Εκμεταλλευόμενοι συγκεκριμένες συμμετρίες και πλεονασμούς στον ορισμό του 23#23, μπορούμε να αναπτύξουμε έναν αλγόριθμο σύντομου δρόμου για να υπολογίζουμε τον 23#23 με μεγάλη αποδοτικότητα. Για να τον παρουσιάσουμε, θεωρείστε την περίπτωση 1667#1667. Από τον ορισμό του 23#23 έχουμε:

Καθαρογράφοντας τις τέσσερις εξισώσεις πλήρως, έχουμε

Παρατηρείστε στο Σχήμα 12.1 ότι

και ομαδοποιώντας τες ξανά, παίρνουμε τις τέσσερις εξισώσεις

Μπορούμε τώρα να προσέξουμε ότι ο μετασχηματισμός μπορεί να υπολογιστεί με μόνο 8 προσθέσεις/αφαιρέσεις και 6 πολλαπλασιασμούς, αντί για τις αναμενόμενες (4-1)*4 = 12 προσθέσεις και 1680#1680 πολλαπλασιασμούς. Στην πραγματικότητα, για αυτή τη μικρή περίπτωση απαιτούνται ακόμα λιγότεροι πολλαπλασιασμοί, αφού 1681#1681, αλλά προσπαθήσαμε να παρουσιάσουμε πώς λειτουργεί ο αλγόριθμος στη γενική του περίπτωση. Η βασική ιδέα είναι ότι ο υπολογισμός του 23#23 της αρχικής ακολουθίας τεσσάρων σημείων έχει μειωθεί στον υπολογισμό των 1682#1682 των δύο υπακολουθιών δύο σημείων, μία περιττή και μία άρτια. Αυτή η ιδιότητα γενικεύεται ως εξής: ο 23#23 μίας ακολουθίας 366#366 σημείων μπορεί να υπολογιστεί χωρίζοντάς την σε δύο 1683#1683 με το μισό μήκος, υπό τον όρο το 366#366 να είναι άρτιο.

Πριν εκφράσουμε και τυπικά τον γενικό αλγόριθμο 22#22, αρχικά θεωρούμε ένα συμπληρωματικό ανάπτυγμα σε τμήματα πινάκων που επιφέρει επιπρόσθετη επίγνωση του θέματος. Για ένα δοσμένο ακέραιο 366#366, ορίζουμε τον πίνακα 1684#1684 ως 1685#1685. ’ρα, για παράδειγμα,

Έστω ότι ο 1687#1687 είναι ο πίνακας μετάθεσης

Τότε έχουμε

δηλ., ο 1692#1692 μπορεί να επανακαθοριστεί ώστε το κάθε μπλοκ να είναι μία διαγώνια κλιμακούμενη έκδοση του 1693#1693. Ένας τέτοιος ιεραρχικός διαχωρισμός μπορεί να επιτευχθεί σε κάθε επίπεδο, δεδομένου ότι ο αριθμός των σημείων είναι άρτιος. Γενικά, ο 1694#1694 είναι η μετάθεση που ομαδοποιεί τις άρτιες στήλες του 1695#1695 πριν από τις περιττές στήλες, και 1696#1696. Άρα, για να εφαρμόσουμε τον 1695#1695 σε μία ακολουθία μήκους 366#366, πρέπει να εφαρμόσουμε μερικά τον 1697#1697 στις άρτιες και περιττές υπακολουθίες του και να κλιμακώσουμε τα αποτελέσματα, όπου χρειάζεται, με τον 1698#1698.

Αυτή η περιοδικά επαναλαμβανόμενη προσέγγιση διαίρει-και-βασίλευε για τον υπολογισμό του 23#23 τυποποιείται στην παρακάτω έκφραση του αλγορίθμου 22#22, όπου υποθέτουμε ότι το 366#366 είναι δύναμη του δύο:

1699#1699


1700#1700


1701#1701


1072#1072


1702#1702


1703#1703


1704#1704


849#849


1705#1705


1706#1706


1707#1707


1708#1708


849#849


849#849

Σημειώνουμε τα παρακάτω σημεία σχετικά με τον προηγούμενο αλγόριθμο:

• Υπάρχουν 1709#1709 επίπεδα επανάληψης, το καθένα από τα οποία εμπλέκει 1673#1673 αριθμητικές διαδικασίες, οπότε το συνολικό κόστος είναι 1710#1710. Αν τα βάρη 1711#1711 έχουν υπολογιστεί από πριν, ο συνολικός αριθμός των πραγματικών διαδικασιών κινητής υποδιαστολής για ένα συνήθες σύνθετο προϊόν πίνακα-διανύσματος.
• Για να είναι πιο ξεκάθαρα τα πράγματα, χρησιμοποιούνται διαφορετικοί πίνακες για τις υπακολουθίες, αλλά στην πράξη ο μετασχηματισμός μπορεί να υπολογιστεί στην ίδια θέση χωρίς να χρησιμοποιήσουμε επιπρόσθετο χώρο αποθήκευσης.
• Η ακολουθία εισόδου υποθέτουμε ότι είναι πολύπλοκη. Αν η ακολουθία εισόδου είναι πραγματική, τότε μπορούμε να εκμεταλλευτούμε επιπλέον συμμετρίες στον 23#23 προκειμένου να μειώσουμε τον αποθηκευτικό χώρο και το πλήθος των διαδικασιών στο μισό.
• Η ακολουθία εξόδου δεν παράγεται με τη φυσική σειρά. Οι περισσότερες ρουτίνες 22#22 το επιτρέπουν αυτό με αυτόματο τρόπο με το να επανακαθορίζουν κατάλληλα είτε την ακολουθία εισόδου είτε την ακολουθία εξόδου. Αυτό το επιπλέον βήμα δεν επηρεάζει τη συνολική πολυπλοκότητα υπολογισμού, επειδή ο απαραίτητος επανακαθορισμός (ανάλογα με την ταξινόμηση) κοστίζει και αυτός 1710#1710.
• Ο αλγόριθμος 22#22 μπορεί να σχηματιστεί χρησιμοποιώντας επανάληψη αντί για αναδρομή, γεγονός που είναι συχνά επιθυμητό προκειμένου να έχουμε μεγαλύτερη αποδοτικότητα ή όταν χρησιμοποιούμε μία γλώσσα προγραμματισμού η οποία δεν υποστηρίζει αναδρομή.

Παρά το όνομά του, ο γρήγορος μετασχηματισμός 21#21 είναι ένας αλγόριθμος, όχι ένας μετασχηματισμός. Είναι ένας συγκεκριμένος τρόπος (ή οικογένεια τρόπων) υπολογισμού του διακριτού μετασχηματισμού 21#21 ενός προϊόντος πίνακα-διανύσματος, του οποίου η άμεση εκτίμηση θα φαινόταν να απαιτεί 1712#1712 αριθμητικές διαδικασίες. Η χρήση του αλγορίθμου 22#22 ελαττώνει την εργασία μόνο στα 1710#1710 που στην πράξη δημιουργεί μία τεράστια διαφορά στο χρόνο που απαιτείται για τον μετασχηματισμό μεγάλων ακολουθιών, όπως φαίνεται στον Πίνακα 12.1.

Εξ' αιτίας της όμοιας μορφής του 23#23 και του αντίστροφού της (διαφέρουν μόνο στο πρόσημο του εκθέτη), ο αλγόριθμος 22#22 μπορεί επίσης να χρησιμοποιηθεί αποδοτικά και στον υπολογισμό του αντιστρόφου του 23#23. Αυτή η δυνατότητα να μεταφερόμαστε γρήγορα από το ένα μέρος στο άλλο ανάμεσα στο πεδίο του χρόνου και στο πεδίο της συχνότητας κάνει πιο πρακτική την εκτέλεση οποιονδήποτε υπολογισμών ή αναλύσεων που μπορεί να απαιτούνται σε οποιοδήποτε πεδίο είναι πιο αξιόπιστο ή αποδοτικό.

ΠΙΝΑΚΑΣ 12.1 Η πολυπλοκότητα του αλγορίθμου 22#22 εναντίον του πολλαπλασιασμού πίνακα-διανύσματος 1713#1713

• Περιορισμοί στη Χρήση του 22#22.