Διδακτικά Βιβλία του Παιδαγωγικού Ινστιτούτου

Αναζήτηση

Βρες
Εμφάνιση

5.1.1 Χειρότερη περίπτωση ενός αλγορίθμου

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

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

Παράδειγμα: έστω ότι δίνεται ο επόμενος απλός αλγόριθμος : Αλγόριθμος Παράδειγμα1 n Aρχή_επανάληψης Διάβασε m n Mέχρις_ότου (m=0) ή (n=0) Εκτύπωσε m Τέλος Παράδειγμα 1

Είναι προφανές ότι η χειρότερη περίπτωση για αυτόν τον αλγόριθμο προκύπτει όταν γίνουν 10 επαναλήψεις (δηλαδή μέχρι να ισχύει το n=0).