Επίδοση αλγορίθμων

Για την κατανόηση της επίδοσης ενός αλγορίθμου χρειάζεται να απαντηθεί ένα σύνολο ερωτημάτων. Τα πρωταρχικά ερωτήματα που προκύπτουν είναι:

πώς υπολογίζεται ο χρόνος εκτέλεσης ενός αλγορίθμου; πώς μπορούν να συγκριθούν μεταξύ τους οι διάφοροι αλγόριθμοι; πώς γνωρίζει κανείς, αν ένας αλγόριθμος είναι "βέλτιστος"; Η απάντηση στα ερωτήματα αυτά προαπαιτεί την καταγραφή ουσιωδών πληροφοριών για το πρόβλημα. Οι πληροφορίες αυτές αφορούν κυρίως στην αναγνώριση της χειρότερης περίπτωσης του αλγορίθμου και στην αποτύπωση του μεγέθους του προβλήματος με βάση το πλήθος των δεδομένων.

Χειρότερη περίπτωση ενός αλγορίθμου Η χειρότερη περίπτωση ενός αλγορίθμου αφορά στο μέγιστο κόστος εκτέλεσης του αλγορίθμου. Το κόστος αυτό πολλές φορές κρίνει την επιλογή και το σχεδιασμό ενός αλγορίθμου. Για να εκφρασθεί η χειρότερη περίπτωση χρειάζεται κάποιο μέγεθος σύγκρισης. Η πιο συνηθισμένη πρακτική είναι η μέτρηση του αριθμού των βασικών πράξεων που θα πρέπει να εκτελέσει ο αλγόριθμος στη χειρότερη περίπτωση. Για παράδειγμα, μία βασική πράξη μπορεί να είναι:

ανάθεση τιμής, σύγκριση μεταξύ δύο μεταβλητών, ή οποιαδήποτε αριθμητική πράξη μεταξύ δύο μεταβλητών.

Μέγεθος εισόδου ενός αλγορίθμου Πρέπει να υπάρχει κάποια ή κάποιες μεταβλητές που να εκφράζουν το μέγεθος (size) του αλγορίθμου. Οι μεταβλητές αυτές παρουσιάζουν τους διαφορετικούς συνδυασμούς τιμών που κρίνουν τη συμπεριφορά ενός αλγορίθμου και δίνονται ως δεδομένα στον αλγόριθμο. Γενικά, τα δεδομένα αποτελούν το μέγεθος της εισόδου ενός αλγορίθμου.

Αποδοτικότητα αλγορίθμων Αν η επίλυση ενός προβλήματος μπορεί να επιτευχθεί με τη χρήση δύο ή περισσοτέρων αλγορίθμων, χρειάζεται να γίνει η επιλογή του καταλληλότερου με βάση την αποδοτικότητά τους. Έτσι, αν ο αλγόριθμος Β έχει το ίδιο αποτέλεσμα με τον αλγόριθμο Α, αλλά δίνει τα αποτελέσματα σε λιγότερο χρόνο, τότε ο Β είναι αποδοτικότερος του Α. Βέβαια όταν συγκρίνονται δύο αλγόριθμοι, θα πρέπει να συγκρίνονται με χρήση των ίδιων δεδομένων και κάτω από τις ίδιες συνθήκες. Γενικά, ο χρόνος εκτέλεσης κάθε αλγορίθμου εξαρτάται από ένα σύνολο παραγόντων που μπορούν να συνοψισθούν στους εξής:

Τύπος ηλεκτρονικού υπολογιστή που θα εκτελέσει το πρόγραμμα του αλγορίθμου, Γλώσσα προγραμματισμού που θα χρησιμοποιηθεί, Δομή προγράμματος και δομές δεδομένων που χρησιμοποιούνται, Χρόνος για πρόσβαση στο δίσκο και στις ενέργειες εισόδου-εξόδου, Είδος συστήματος, ενός χρήστη ή πολλών χρηστών. Επομένως, θα πρέπει να ικανοποιούνται οι παρακάτω προϋποθέσεις:

και τα δύο προγράμματα να έχουν συνταχθεί στην ίδια γλώσσα προγραμματισμού, να έχουν μεταφραστεί με τον ίδιο τρόπο, να χρησιμοποιείται η ίδια υπολογιστική πλατφόρμα, να έχουν τις ίδιες τιμές εισόδου-εξόδου.

Βιβλιογραφία: http://ebooks.edu.gr/ebooks/v/html/8547/2718/Pliroforiki_G-Lykeiou_html-empl/index5_1.html