Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 26:
ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ (OPTIMALITY)
Για να αναλύσουμε την πολυπλοκότητα ενός προβλήματος, όπως τίθεται από έναν συγκεκριμένο αλγόριθμο, διαλέγουμε μια κλάση αλγορίθμων (συχνά καθορίζοντας τον τύπο των πράξεων που επιτρέπεται να εκτελούν οι αλγόριθμοι) και ένα μέτρο της πολυπλοκότητας, όπως πχ τις μετρούμενες πράξεις. Τότε μπορούμε να ρωτήσουμε πόσες πράξεις χρειάζονται για να λυθεί ένα πρόβλημα. Υπάρχει ο "καλύτερος" δυνατός αλγόριθμος; Λέμε ότι ένας αλγόριθμος είναι βέλτιστος (στη χειρότερη περίπτωση), αν δεν υπάρχει άλλος αλγόριθμος στην κλάση που μελετάμε που να εκτελεί λιγότερες πράξεις (στη χειρότερη περίπτωση).
Πριν καταλήξουμε στο ποιος είναι ο βέλτιστος, μήπως πρέπει να εξετάσουμε καθέναν από την κλάση ξεχωριστά; Ευτυχώς όχι. Μπορούμε να αποδείξουμε θεωρήματα που καθορίζουν ένα κάτω όριο στον αριθμό των πράξεων που εκτελούνται. Τότε κάθε αλγόριθμος που εκτελεί αυτον τον αριθμό των πράξεων είναι βέλτιστος. Επομένως υπάρχουν δύο δουλειές που πρέπει να γίνουν για να βρούμε έναν καλό αλγόριθμο στην κλάση των αλγορίθμων που μελετάμε, ή αλλιώς, να παντήσουμε στη θεωρητική ερώτηση : Πόση δουλειά είναι απαραίτητη και αρκετή για να λυθεί ένα πρόβλημα;
α) Καθορίζουμε έναν φαινομενικά αποδοτικό αλγόριθμο, έστω Α. Αναλύουμε τον Α και βρίσκουμε μια συνάρτηση W, τέτοια που για είσοδο τάξης n, ο Α να εκτελεί το πολύ W(n) βασικές πράξεις.
β) Για κάποια συνάρτηση F, αποδεικνύουμε ένα θεώρημα, που λέει ότι για οποιοδήποτε αλγόριθμο στη υπό μελέτη κλάση, υπάρχει μια είσοδος τάξης n για την οποία ο αλγόριθμος πρέπει να εκτελέσει τουλάχιστον F(n) βασικές πράξεις.
Αν οι συναρτήσεις F και W είναι ίσες, τότε ο αλγόριθμος Α είναι βέλτιστος. Αν όχι, σημαίνει ότι υπάρχει καλύτερος αλγόριθμος ή καλύτερο κάτω όριο. Παρατηρείστε ότι η ανάλυση ενός αλγορίθμου δίνει ένα άνω όριο των βασικών πράξεων και ένα θεώρημα για την F δίνει ένα κάτω όριο στις βασικές πράξεις για κάθε αλγόριθμο στην κλάση, στη χειρότερη περίπτωση.
Η έννοια του κάτω ορίου για τη συμπεριφορά της χειρότερης περίπτωσης των αλγορίθμων στη συγκεκριμένη κλάση, είναι πολύ σημαντική στην υπολογιστική πολυπλοκότητα. Πρέπει να κρατήσουμε καλά στο μυαλό μας ότι: " η F είναι ένα κάτω όριο για μια κλάση αλγορίθμων", σημαίνει ότι για κάθε αλγόριθμο στην κλάση και για κάθε είσοδο τάξης n, υπάρχει κάποια είσοδος τάξης n, για την οποία ο αλγόριθμος πρέπει να εκτελέσει τουλάχιστον F(n) βασικές πράξεις.
| |||