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

Στα προηγούμενα κεφάλαια του βιβλίου παρουσιάσθηκαν πολλοί αλγόριθμοι για την επίλυση ενός προβλήματος, όπως για παράδειγμα σχετικά με την αναζήτηση και την ταξινόμηση. Στο σημείο αυτό θα παρουσιάσουμε έναν τρόπο εκτίμησης της επίδοσης (performance) ή της αποδοτικότητας (efficiency) των αλγορίθμων.

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

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