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

Αναζήτηση

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

5.1.3 Χρόνος εκτέλεσης προγράμματος ενός αλγορίθμου

Έστω ότι έχουμε τον εξής αλγόριθμο: Αλγόριθμος Παράδειγμα2 x Για i από 0 μέχρι 4 Εκτύπωσε i z Τέλος_επανάληψης Εκτύπωσε x Εκτύπωσε y Εκτύπωσε z Τέλος Παράδειγμα2

Θα υπολογισθεί η επίδοσή του με βάση τον αριθμό των πράξεων που θα εκτελεσθούν. Με δεδομένο ότι ο βρόχος του προγράμματος θα εκτελεσθεί 5 φορές, προκύπτει η παρακάτω ανάλυση :

Εντολή αλγορίθμου Αριθμός πράξεων ανάθεση τιμών στα x και y2 Βρόχος επανάληψης αρχική τιμή i 1 έλεγχος i 6 αύξηση i 5 εκτύπωση i 5 υπολογισμός z (2Χ5) 10 Εκτύπωση x, y, z3 ΣΥΝΟΛΟ 32

Οι βρόχοι επανάληψης αποτελούν το κρίσιμο σημείο για τον χαρακτηρισμό της επίδοσης ενός αλγορίθμου Έτσι αν ο αλγόριθμος αυτός γενικευθεί ώστε ο βρόχος να εκτελεσθεί n φορές, ο χρόνος εκτέλεσης θα εξαρτάται από το μέγεθος του n. Ο πίνακας 5.2 παρουσιάζει τους χρόνους εκτέλεσης του αλγορίθμου αυτού για διαφορετικά μεγέθη του n, θεωρώντας ότι ο χρόνος είναι ο αριθμός των πράξεων σε μικρο-δευτερόλεπτα :

Πιν. 5.2. Χρόνοι εκτέλεσης αλγορίθμου ανάλογα με το μέγεθος μέγεθος n Χρόνος εκτέλεσης 5 42 μικρο-δευτερόλεπτα 1077 μικρο-δευτερόλεπτα 100 707 μικρο-δευτερόλεπτα 1.000.0007 δευτερόλεπτα (περίπου)