Για την κατανόηση της επίδοσης ενός αλγορίθμου χρειάζεται να απαντηθεί το πρωταρχικά ερώτημα για τον τρόπο υπολογισμού του χρόνου εκτέλεσης ενός αλγορίθμου.
Μία βασική πράξη είναι η επανάληψη ενός βρόχου τόσες φορές όσες δίνονται από το συγκεκριμένο όριο τιμών μίας μεταβλητής.
Το μέγεθος του αλγορίθμου εκφράζεται από κάποια ή κάποιες μεταβλητές και γενικά τα δεδομένα συνιστούν το μέγεθος της εισόδου ενός αλγορίθμου.
Οι βρόχοι επανάληψης δεν αποτελούν σημαντικό κριτήριο για το χαρακτηρισμό της επίδοσης ενός αλγορίθμου.
Για να έχει έννοια κάθε σύγκριση μεταξύ δύο προγραμμάτων αλγορίθμων θα πρέπει και τα δύο προγράμματα να έχουν συνταχθεί στην ίδια γλώσσα προγραμματισμού και να χρησιμοποιείται η ίδια υπολογιστική πλατφόρμα
Η χειρότερη περίπτωση ενός αλγορίθμου αφορά στο ελάχιστο κόστος εκτέλεσης του αλγορίθμου, κόστος που μετράται σε υπολογιστικούς πόρους.
§ 5.3 Πολυπλοκότητα αλγορίθμων
Ένας τρόπος εκτίμησης της επίδοσης ενός αλγορίθμου είναι ο θεωρητικός ή αλλιώς «εκ των προτέρων» όπου χρησιμοποιείται μία μεταβλητή που εκφράζει το μέγεθος του προβλήματος.
Αν η πολυπλοκότητα ενός αλγορίθμου είναι f(n), τότε λέγεται ότι είναι τάξης 0(g(n)) αν υπάρχουν δύο θετικοί ακέραιοι c και no, έτσι ώστε για κάθε n> no να ισχύει:
|f(n)|< c |g(n)| .
Η πολυπλοκότητα της Ταξινόμησης ευθείας ανταλλαγής είναι Ο(n).
Η πολυπλοκότητα της Δυαδικής αναζήτησης είναι O(logn).
O(n) είναι η γραμμική πολυπλοκότητα που θεωρείται η καλύτερη επίδοση για έναν αλγόριθμο που πρέπει να εξετάσει ή να δώσει στην έξοδο n στοιχεία.
Ο συμβολισμός O(n² ) εκφράζει την κυβική πολυπλοκότητα και πρέπει να χρησιμοποιείται μόνο για προβλήματα μεγάλου μεγέθους.
Τα δεδομένα συνιστούν το μέγεθος της πολυπλοκότητας ενός αλγορίθμου.
Ο απλούστερος τρόπος μέτρησης της επίδοσης ενός αλγορίθμου είναι ο εμπειρικός ή αλλιώς ο λεγόμενος εκ των προτέρων που υλοποιείται και εφαρμόζεται σε ένα σύνολο δεδομένων ώστε να υπολογισθεί ο απαιτούμενος χρόνος επεξεργασίας και η πολυπλοκότητα.
Διάλεξε όλα όσα χρειάζονται μεταξύ των προτεινόμενων:
Μία βασική πράξη μπορεί να είναι:
Α) βρόχος επανάληψης
Β) ανάθεση τιμής
Γ) σύγκριση μεταξύ δύο μεταβλητών
Δ) συνθήκη Αν..αλλιώς
Ε) οποιαδήποτε αριθμητική πράξη μεταξύ δύο μεταβλητών
Ο χρόνος εκτέλεσης κάθε αλγορίθμου εξαρτάται από ένα σύνολο παραγόντων που περιλαμβάνουν τα εξής:
Α) Τύπος ηλεκτρονικού υπολογιστή που θα εκτελέσει το πρόγραμμα του αλγορίθμου
Β) Χρονική στιγμή εκτέλεσης του αλγορίθμου
Γ) Συνθήκες ανταγωνισμού με άλλους αλγορίθμους
Δ) Γλώσσα προγραμματισμού που θα χρησιμοποιηθεί
Ε) Δομή προγράμματος και δομές δεδομένων που χρησιμοποιεί
Ζ) Αριθμός εντολών του αλγορίθμου
Η) Χρόνος για πρόσβαση στο δίσκο και στις ενέργειες εισόδου-εξόδου
Θ) Είδος συστήματος, ενός χρήστη ή πολλαπλών χρηστών
