Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 31:
</nowiki>
<nowiki>
Ο ορισμός των θέσεων μνήμης που χρησιμοποιεί ένα πρόγραμμα, όπως και ο αριθμός των δευτερολέπτων που απαιτούνται, εξαρτάται από την υλοποίηση που επιλέγουμε. Παρόλο αυτά μπορούμε να εξάγουμε κάποια συμπεράσματα, εξετάζοντας έναν αλγόριθμο. Ένα πρόγραμμα χρειάζεται μνήμη για τις εντολές, τις σταθερές και τις μεταβλητές και τα δεδομένα. Χρειάζεται επιπλέον χώρο για την επεξεργασία των δεδομένων, και για την αποθήκευση των ενδιάμεσων αποτελεσμάτων. Τα δεδομένα εισόδου μπορούν να παρασταθούν με διάφορες μορφές που έχουν διαφορετικές απιτήσεις σε μνήμη. Αν έχουν μια φυσική μορφή - όπως ένα αρραυ αριθμών ή έναν πίνακα - τότε αναλύουμε και τον επιπλέον χώρο που χρησιμοποιείται, εκτός από το πρόγραμμα και την είσοδό του. Αν η επιπλέον μνήμη είναι σταθερή ως προς το μέγεθος της εισόδου, τότε λέμε ότι ο αλγόριθμος δουλεύει in place. Αυτός ο όρος χρησιμοποιείται κυρίως σε αλγόριθμους διάταξης. Αν η είσοδος μπορεί να παρασταθεί με διάφορους τρόπους (πχ γράφους) τότε, φυσικά, θα υπολογίσουμε τη μνήμη για την ίδια την είσοδο καθώς και την επιπλέον μνήμη. Γενικά, θα αναφερόμαστε σε ποσότητα μνήμης χωρίς να προσδιορίζουμε ακριβώς τα KB. Πρέπει να θεωρούμε τη θέση μνήμης αρκετά μεγάλη για να χωρέσει έναν αριθμό. Αν το μέγεθος της μνήμης εξαρτάται από τη συγκεκριμένη είσοδο, μπορεί να γίνει η ανάλυση χειρότερης περίπτωσης (worst- case) και μέσης περίπτωσης (average - case).
</nowiki>
<nowiki>
▲ <nowiki>'''ΧΡΗΣΗ ΜΝΗΜΗΣ'''
▲ Ο ορισμός των θέσεων μνήμης που χρησιμοποιεί ένα πρόγραμμα, όπως και ο αριθμός των δευτερολέπτων που απαιτούνται, εξαρτάται από την υλοποίηση που επιλέγουμε. Παρόλο αυτά μπορούμε να εξάγουμε κάποια συμπεράσματα, εξετάζοντας έναν αλγόριθμο. Ένα πρόγραμμα χρειάζεται μνήμη για τις εντολές, τις σταθερές και τις μεταβλητές και τα δεδομένα. Χρειάζεται επιπλέον χώρο για την επεξεργασία των δεδομένων, και για την αποθήκευση των ενδιάμεσων αποτελεσμάτων. Τα δεδομένα εισόδου μπορούν να παρασταθούν με διάφορες μορφές που έχουν διαφορετικές απιτήσεις σε μνήμη. Αν έχουν μια φυσική μορφή - όπως ένα αρραυ αριθμών ή έναν πίνακα - τότε αναλύουμε και τον επιπλέον χώρο που χρησιμοποιείται, εκτός από το πρόγραμμα και την είσοδό του. Αν η επιπλέον μνήμη είναι σταθερή ως προς το μέγεθος της εισόδου, τότε λέμε ότι ο αλγόριθμος δουλεύει in place. Αυτός ο όρος χρησιμοποιείται κυρίως σε αλγόριθμους διάταξης. Αν η είσοδος μπορεί να παρασταθεί με διάφορους τρόπους (πχ γράφους) τότε, φυσικά, θα υπολογίσουμε τη μνήμη για την ίδια την είσοδο καθώς και την επιπλέον μνήμη. Γενικά, θα αναφερόμαστε σε ποσότητα μνήμης χωρίς να προσδιορίζουμε ακριβώς τα KB. Πρέπει να θεωρούμε τη θέση μνήμης αρκετά μεγάλη για να χωρέσει έναν αριθμό. Αν το μέγεθος της μνήμης εξαρτάται από τη συγκεκριμένη είσοδο, μπορεί να γίνει η ανάλυση χειρότερης περίπτωσης (worst- case) και μέσης περίπτωσης (average - case).</nowiki>
Συχνά, όχι πάντα, ο άμεσος τρόπος επίλυσης ενός προβλήματος δεν είναι και ο πιο αποδοτικός. Η απλότητα ενός αλγορίθμου είναι ένα επιθυμητό χαρακτηριστικό. Κάνει την απόδειξη της ορθότητας ευκολότερη, όπως επίσης ευκολότερο το γράψιμο, την εκσφαλμάτωση και τη μετατροπή ενός προγράμματος. ¨οταν διαλέγουμε έναν αλγόριθμο πρέπει να συνυπολογίσουμε το χρόνο που χρειάζεται η εκσφαλμάτωση, αλλά αν το πρόγραμμα χρησιμοποιείται πολύ συχνά, ο κρισιμότερος παράγοντας είναι η αποδοτικότητα.
</nowiki>
▲ <nowiki>'''ΑΠΛΟΤΗΤΑ'''
<nowiki>
▲ Συχνά, όχι πάντα, ο άμεσος τρόπος επίλυσης ενός προβλήματος δεν είναι και ο πιο αποδοτικός. Η απλότητα ενός αλγορίθμου είναι ένα επιθυμητό χαρακτηριστικό. Κάνει την απόδειξη της ορθότητας ευκολότερη, όπως επίσης ευκολότερο το γράψιμο, την εκσφαλμάτωση και τη μετατροπή ενός προγράμματος. ¨οταν διαλέγουμε έναν αλγόριθμο πρέπει να συνυπολογίσουμε το χρόνο που χρειάζεται η εκσφαλμάτωση, αλλά αν το πρόγραμμα χρησιμοποιείται πολύ συχνά, ο κρισιμότερος παράγοντας είναι η αποδοτικότητα.</nowiki>
▲ <nowiki>'''ΒΕΛΤΙΣΤΟΠΟΙΗΣΗ (OPTIMALITY)'''
Για να αναλύσουμε την πολυπλοκότητα ενός προβλήματος, όπως τίθεται από έναν συγκεκριμένο αλγόριθμο, διαλέγουμε μια κλάση αλγορίθμων (συχνά καθορίζοντας τον τύπο των πράξεων που επιτρέπεται να εκτελούν οι αλγόριθμοι) και ένα μέτρο της πολυπλοκότητας, όπως πχ τις μετρούμενες πράξεις. Τότε μπορούμε να ρωτήσουμε πόσες πράξεις χρειάζονται για να λυθεί ένα πρόβλημα. Υπάρχει ο "καλύτερος" δυνατός αλγόριθμος; Λέμε ότι ένας αλγόριθμος είναι βέλτιστος (στη χειρότερη περίπτωση), αν δεν υπάρχει άλλος αλγόριθμος στην κλάση που μελετάμε που να εκτελεί λιγότερες πράξεις (στη χειρότερη περίπτωση).
Πριν καταλήξουμε στο ποιος είναι ο βέλτιστος, μήπως πρέπει να εξετάσουμε καθέναν από την κλάση ξεχωριστά; Ευτυχώς όχι. Μπορούμε να αποδείξουμε θεωρήματα που καθορίζουν ένα κάτω όριο στον αριθμό των πράξεων που εκτελούνται. Τότε κάθε αλγόριθμος που εκτελεί αυτον τον αριθμό των πράξεων είναι βέλτιστος. Επομένως υπάρχουν δύο δουλειές που πρέπει να γίνουν για να βρούμε έναν καλό αλγόριθμο στην κλάση των αλγορίθμων που μελετάμε, ή αλλιώς, να παντήσουμε στη θεωρητική ερώτηση : Πόση δουλειά είναι απαραίτητη και αρκετή για να λυθεί ένα πρόβλημα;
| |||