ΑΕΠΠ_ Γ΄ ΛΥΚΕΙΟΥ

Λεπτομέρειες

Τελευταία Ενημέρωση στις Δευτέρα, 30 Μαΐου 2016 05:07

ΚΕΦΑΛΑΙΟ 5: ΑΠΟΔΟΤΙΚΟΤΗΤΑ – ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΑΛΓΟΡΙΘΜΩΝ

1. Τι δείχνει η επίδοση αλγορίθμου;

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

2. Πώς μετράμε τη χειρότερη περίπτωση ενός αλγορίθμου;

Μετράμε τις βασικές πράξεις  που πρέπει να εκτελέσει ο αλγόριθμος στην χειρότερη περίπτωση. Οι βασικές πράξεις είναι:

1. Ανάθεση τιμής
2. Έλεγχος (σύγκριση δύο μεταβλητών)
3. Οποιαδήποτε αριθμητική πράξη

Το μέγεθος εισόδου το πλήθος των δεδομένων που παίρνει ως είσοδο ο αλγόριθμος.

Ο χρόνος εκτέλεσης ενός προγράμματος είναι το άθροισμα των χρόνων εκτέλεσης των επιμέρους τμημάτων του.

Παράδειγμα1

αλγόριθμοςπροσθεση
διαβασε α,β,γ,δ

κ<-α+β+γ+δ

εμφάνισε κ

τέλος

χειρότερη περίπτωση: δεν υπάρχει

Μέγεθος εισόδου: 4 μεταβλητές

Χρόνος εκτέλεσης:  αναθεση τιμών 4

                                     Πράξεις 3

 Εκτύπωση 1

Συνολο: 8

Παράδειγμα 2

αλγόριθμοςαθροισμα_αριθμών από 1 μέχρι 10

  α<-0
  ι<-1

  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    α<-α+ι
    ι<-ι+1
  ΜΕΧΡΙΣ_ΟΤΟΥι>10

  εμφάνισε" αθροισμα ",α

ΤΕΛΟΣ

χειρότερη περίπτωση: δεν υπάρχει

Μέγεθος εισόδου: 1 μεταβλητή

Χρόνος εκτέλεσης: 

Εντολή	Αριθμόςπράξεων
Ανάθεση τιμών α,ι	2
Βρόχος επανάληψης
Υπολογισμός & ανάθεση τιμής στο α	2*10=20
Υπολογισμός & ανάθεση τιμής στο ι	2*10=20
Έλεγχος	10
Εκτύπωση	1
ΣΥΝΟΛΟ

Παράδειγμα 3

Αλγοριθμος αναζητηση

   Εμφάνισε "δωσε  τα 5 στοιχεία του πινακα "

  γιαιαπό 1 μέχρι 5
   διάβασε Α[ι]
  τέλος_επανάληψης

  εμφάνισε"ποιον αριθμο ψαχνεις;"

  ΔΙΑΒΑΣΕχ

  βρεθ<-ΨΕΥΔΗΣ
  θεση<-0
  ι<-1

Όσο  ι<=5ΚΑΙβρεθ=ΨΕΥΔΗΣεπανάλαβε
    ΑΝΑ[ι]=χΤΟΤΕ
      βρεθ<-ΑΛΗΘΗΣ
      θεση<-ι
    ΑΛΛΙΩΣ
      ι<-ι+1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  εμφάνισε βρεθ," ",θεση
ΤΕΛΟΣ

χειρότερη περίπτωση:Ο αριθμός που ψάχνουμε να βρίσκεται στην τελευταία θέση του πίνακα λη να μην βρίκεται στον πίνακα

Μέγεθος εισόδου: 1 μεταβλητή χ και 5 στοιχεία του πίνακα Α

Χρόνος εκτέλεσης: 

Εντολή	Αριθμόςπράξεων
Εμφάνισε	3
Βρόχος 1ος
Αρχική τιμή ι	1
Έλεγχος	6
Υπολογισμός & ανάθεση τιμής στο ι	5*2
Ανάθεση τιμής στο Α[ι]	5
Αναθεση τιμής στο χ	1
Ανάθεση τιμής σε βρεθ, θεση,ι	3
2ος βρόχος
Έλεγχος ι & βρεθ	6*2
Συγκριση Α[ι] με χ	5
Υπολογισμός & Ανάθεση τιμής στο ι	5*2
Ανάθεση τιμής σε βρεθ, θεση,ι	3
ΣΥΝΟΛΟ

ΑΣΚΗΣΗ: Να υπολογίσετε

1. την χειρότερη περίπτωση, 2. το μέγεθος εισόδου και 3. Τον χρόνο εκτέλεσης του αλγόριθμου ΒΑΘΜΟΙ.

5. Πότε ένας αλγόριθμος θεωρείται αποδοτικότερος από έναν άλλο;

Ένας αλγόριθμος Α θεωρείται αποδοτικότερος από έναν άλλο Β όταν ο Α με το ίδιο μέγεθος εισόδου:

1. Χρησιμοποιεί μικρότερο χώρο στη μνήμη.

2. Δίνει γρηγορότερα τα αποτελέσματα δηλ. έχει μικρότερο χρόνο εκτέλεσης.

6. Από τι εξαρτάται ο χρόνος εκτέλεσης ενός αλγορίθμου;

      Από τον τύπο του Η/Υ που θα χρησιμοποιηθεί.

      Από τη Γλώσσα Προγραμματισμού

      Από την δομή του προγράμματος και τις δομές δεδομένων που θα χρησιμοποιηθούν.

      Από το πλήθος  εντολών εισόδου-εξόδου (πρόσβαση στο δίσκο)

v  Εμπειρικά δηλαδή αφού εκτελεστεί

v  Θεωρητικά υπολογίζοντας τη πολυπλοκότητα του αλγορίθμου

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