Κεφάλαιο 5 Ανάλυση Αλγορίθμων
5.1 Επίδοση (Performance) ή αποδοτικότητα (Efficiency) των αλγορίθμων.
Για να μπορέσουμε να κατανοήσουμε τι ακριβώς σημαίνει ο όρος επίδοση ενός αλγορίθμου θα πρέπει πρώτα να απαντήσουμε μερικά ερωτήματα όπως :
Πώς υπολογίζουμε την χειρότερη περίπτωση ενός αλγορίθμου;
Η χειρότερη περίπτωση ενός αλγορίθμου αφορά στο μέγιστο κόστος εκτέλεσης του αλγορίθμου, κόστος που μετράται σε υπολογιστικούς πόρους. Για να εκφρασθεί αυτή η χειρότερη περίπτωση χρειάζεται κάποιο μέγεθος σύγκρισης και αναφοράς που να χαρακτηρίζει τον αλγόριθμο. Η πλέον συνηθισμένη πρακτική είναι η μέτρηση του αριθμού των βασικών πράξεων που θα πρέπει να εκτελέσει ο αλγόριθμος στη χειρότερη περίπτωση.
Για παράδειγμα , μια βασική πράξη μπορεί να είναι :
5.1.2 Μέγεθος εισόδου ενός αλγορίθμου
Πρέπει να υπάρχει κάποια ή κάποιες μεταβλητές που να εκφράζουν το μέγεθος ενός αλγορίθμου.
Οι μεταβλητές αυτές απεικονίζουν τους διαφορετικούς συνδυασμούς τιμών που κρίνουν τη συμπεριφορά ενός αλγορίθμου και δίνονται ως δεδομένα στον αλγόριθμο.
5.1.3 Χρόνος εκτέλεσης ενός αλγορίθμου
Έστω ότι έχουμε τον παρακάτω αλγόριθμο:
Αλγόριθμος Παρ_1
S<--0
Για i από 1 μέχρι 400
Αν i mod 8 = 0 τότε
S<--S+i
Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε ‘ το άθροισμα είναι:’,S
Τέλος Παρ_1
Με δεδομένο ότι ο βρόχος του προγράμματος θα πραγματοποιηθεί 400 φορές έχουμε:
Εντολή Αλγορίθμου Αριθμός πράξεων
Ανάθεση τιμής στο s 1
Αρχική τιμή i 1
Έλεγχος i (στην επανάληψη) 400
Έλεγχος i (στην επιλογή) 400
Αύξηση s 50
Αύξηση i (βήμα) 400
Εμφάνιση αποτελέσματος 1
Σύνολο 1253
Ας δούμε και μια διαφορετική λύση για το ίδιο πρόβλημα:
Αλγόριθμος Παρ_2
S<--0
Για i από 8 μέχρι 400 με_βήμα 8
S<--S+i
Τέλος_επανάληψης
Εμφάνισε ‘το άθροισμα είναι:’,S
Τέλος παρ_2
Η ανάλυση εδώ θα έχει ως εξής :
Εντολή Αλγορίθμου Αριθμοί πράξεων
Ανάθεση τιμής στο s 1
Αρχική τιμή i 1
Έλεγχος i (στην επανάληψη) 50
Αύξηση s 50
Αύξηση i (βήμα) 50
Εμφάνιση αποτελέσματος 1
Σύνολο 153
Βλέπουμε ξεκάθαρα πλέον τι σημαίνει αποδοτικότερος αλγόριθμος και πως ο αριθμός των βρόχων επηρεάζει το χρόνο εκτέλεσης.
Μπορείτε να κατεβάσετε τα παρακάτω αρχεία και να «τρέξετε» τα προγράμματα στη γλωσσομάθεια για να δείτε τη διαφορά στους χρόνους εκτέλεσης.
Για να μπορέσουμε να κατανοήσουμε τι ακριβώς σημαίνει ο όρος επίδοση ενός αλγορίθμου θα πρέπει πρώτα να απαντήσουμε μερικά ερωτήματα όπως :
- Πώς υπολογίζεται ο χρόνος εκτέλεσης ενός αλγορίθμου.
- Πως μπορούν να συγκριθούν μεταξύ τους οι διάφοροι αλγόριθμοι.
- Πως μπορεί να γνωρίζει κανείς αν ένας αλγόριθμος είναι «βέλτιστος»
- Αναγνώριση της «χειρότερης» περίπτωσης του αλγορίθμου, και
- Την αποτύπωση του μεγέθους του προβλήματος με βάση το πλήθος των δεδομένων .
Πώς υπολογίζουμε την χειρότερη περίπτωση ενός αλγορίθμου;
Η χειρότερη περίπτωση ενός αλγορίθμου αφορά στο μέγιστο κόστος εκτέλεσης του αλγορίθμου, κόστος που μετράται σε υπολογιστικούς πόρους. Για να εκφρασθεί αυτή η χειρότερη περίπτωση χρειάζεται κάποιο μέγεθος σύγκρισης και αναφοράς που να χαρακτηρίζει τον αλγόριθμο. Η πλέον συνηθισμένη πρακτική είναι η μέτρηση του αριθμού των βασικών πράξεων που θα πρέπει να εκτελέσει ο αλγόριθμος στη χειρότερη περίπτωση.
Για παράδειγμα , μια βασική πράξη μπορεί να είναι :
- Η ανάθεση τιμής,
- Η σύγκριση μεταξύ δυο μεταβλητών , ή
- Οποιαδήποτε αριθμιτική πράξη μεταξύ δυο μεταβλητών
5.1.2 Μέγεθος εισόδου ενός αλγορίθμου
Πρέπει να υπάρχει κάποια ή κάποιες μεταβλητές που να εκφράζουν το μέγεθος ενός αλγορίθμου.
Οι μεταβλητές αυτές απεικονίζουν τους διαφορετικούς συνδυασμούς τιμών που κρίνουν τη συμπεριφορά ενός αλγορίθμου και δίνονται ως δεδομένα στον αλγόριθμο.
5.1.3 Χρόνος εκτέλεσης ενός αλγορίθμου
Έστω ότι έχουμε τον παρακάτω αλγόριθμο:
Αλγόριθμος Παρ_1
S<--0
Για i από 1 μέχρι 400
Αν i mod 8 = 0 τότε
S<--S+i
Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε ‘ το άθροισμα είναι:’,S
Τέλος Παρ_1
Με δεδομένο ότι ο βρόχος του προγράμματος θα πραγματοποιηθεί 400 φορές έχουμε:
Εντολή Αλγορίθμου Αριθμός πράξεων
Ανάθεση τιμής στο s 1
Αρχική τιμή i 1
Έλεγχος i (στην επανάληψη) 400
Έλεγχος i (στην επιλογή) 400
Αύξηση s 50
Αύξηση i (βήμα) 400
Εμφάνιση αποτελέσματος 1
Σύνολο 1253
Ας δούμε και μια διαφορετική λύση για το ίδιο πρόβλημα:
Αλγόριθμος Παρ_2
S<--0
Για i από 8 μέχρι 400 με_βήμα 8
S<--S+i
Τέλος_επανάληψης
Εμφάνισε ‘το άθροισμα είναι:’,S
Τέλος παρ_2
Η ανάλυση εδώ θα έχει ως εξής :
Εντολή Αλγορίθμου Αριθμοί πράξεων
Ανάθεση τιμής στο s 1
Αρχική τιμή i 1
Έλεγχος i (στην επανάληψη) 50
Αύξηση s 50
Αύξηση i (βήμα) 50
Εμφάνιση αποτελέσματος 1
Σύνολο 153
Βλέπουμε ξεκάθαρα πλέον τι σημαίνει αποδοτικότερος αλγόριθμος και πως ο αριθμός των βρόχων επηρεάζει το χρόνο εκτέλεσης.
Μπορείτε να κατεβάσετε τα παρακάτω αρχεία και να «τρέξετε» τα προγράμματα στη γλωσσομάθεια για να δείτε τη διαφορά στους χρόνους εκτέλεσης.
|
| ||||
5.1.4 Αποδοτικότητα αλγορίθμων
Όταν συγκρίνονται δυο αλγόριθμοι, θα πρέπει να συγκρίνονται με χρήση των ίδιων δεδομένων και κάτω από τις ίδιες συνθήκες.
Γενικά, ο χρόνος εκτέλεσης κάθε αλγορίθμου εξαρτάται από ένα σύνολο παραγόντων που μπορούν να συνοψισθούν στους εξής:
Όταν συγκρίνονται δυο αλγόριθμοι, θα πρέπει να συγκρίνονται με χρήση των ίδιων δεδομένων και κάτω από τις ίδιες συνθήκες.
Γενικά, ο χρόνος εκτέλεσης κάθε αλγορίθμου εξαρτάται από ένα σύνολο παραγόντων που μπορούν να συνοψισθούν στους εξής:
- Τύπος του ηλεκτρονικού υπολογιστή που θα εκτελέσει το πρόγραμμα του αλγορίθμου,
- Γλώσσα προγραμματισμού που θα χρησιμοποιηθεί,
- Δομή προγράμματος και δομές δεδομένων που θα χρησιμοποιηθούν,
- Χρόνος για πρόσβαση στο δίσκο και στις ενέργειες εισόδου εξόδου,
- Είδος συστήματος , ενός χρήστη ή πολλών χρηστών
- Και τα δυο προγράμματα να έχουν συνταχθεί στην ίδια γλώσσα προγραμματισμού,
- Να έχει χρησιμοποιηθεί ο ίδιος μεταφραστής της γλώσσας προγραμματισμού,
- Να χρησιμοποιείται η ίδια υπολογιστική πλατφόρμα,
- Ακριβώς τα ίδια δεδομένα να αποτελούν είσοδο κατά τον έλεγχο των δύο αλγορίθμων.
Ασκήσεις στο κεφάλαιο 5
Κατεβάστε το αρχείο:
| Κεφ5_Ασκήσεις.pdf |