Το κεφάλαιο δείχνει πώς μετράμε την επίδοση ενός αλγορίθμου, πώς ελέγχουμε την ορθότητά του, τι σημαίνει πολυπλοκότητα με τον συμβολισμό Ο και ποια είναι τα κύρια είδη αλγορίθμων.
Γ΄ ΛΥΚΕΙΟΥΠΛΗΡΟΦΟΡΙΚΗ15 ΛΕΠΤΑ
Το μάθημα είναι στο σχολικό βιβλίο. Δεν το αντιγράφουμε εδώ. Άνοιξε το επίσημο
κεφάλαιο και γύρνα για την εξάσκηση.
Δική μας σύνοψη της ενότητας, για επανάληψη. Το βιβλίο δεν αντιγράφεται: άνοιξέ το παραπάνω.
Τι έγινε
Η επίδοση ενός αλγορίθμου εκφράζεται με τον αριθμό των βασικών πράξεων (ανάθεση, σύγκριση, αριθμητική πράξη) στη χειρότερη περίπτωση, σε σχέση με το μέγεθος της εισόδου.
Οι βρόχοι επανάληψης είναι το κρίσιμο σημείο: ο χρόνος εκτέλεσης μεγαλώνει με το πλήθος των επαναλήψεων n.
Δύο προγράμματα συγκρίνονται σωστά μόνο με ίδια γλώσσα, ίδιο μεταφραστή, ίδια υπολογιστική πλατφόρμα και ίδια δεδομένα.
Οι δοκιμαστικές εκτελέσεις δεν εγγυώνται ορθότητα· η απόδειξη πρέπει να δείχνει ότι ο αλγόριθμος τερματίζει και δίνει αποδεκτά αποτελέσματα.
Η εκ των υστέρων μέτρηση εξαρτάται από υλικό και προγραμματιστή, γι' αυτό χρησιμοποιείται η εκ των προτέρων εκτίμηση με τον συμβολισμό Ο.
Κύριες τάξεις πολυπλοκότητας: Ο(1), O(log n), O(n), O(n log n), O(n²), O(n³) και Ο(2^n), που σπάνια χρησιμοποιείται στην πράξη.
Είδη αλγορίθμων: παράλληλοι, πολυωνυμικοί και εκθετικοί· για δυσχείριστα προβλήματα χρησιμοποιούνται προσεγγιστικοί και ευριστικοί αλγόριθμοι.
Όροι
χειρότερη περίπτωση
οι είσοδοι που οδηγούν τον αλγόριθμο στον μέγιστο αριθμό βασικών πράξεων
μέγεθος εισόδου
τα δεδομένα που δίνονται στον αλγόριθμο, π.χ. το πλήθος των στοιχείων προς ταξινόμηση
βασική πράξη
ανάθεση τιμής, σύγκριση ή αριθμητική πράξη μεταξύ δύο μεταβλητών
αποδοτικότητα
ένας αλγόριθμος είναι αποδοτικότερος αν δίνει το ίδιο αποτέλεσμα σε λιγότερο χρόνο ή με λιγότερη μνήμη
ορθότητα
η απόδειξη ότι ο αλγόριθμος τερματίζει και δίνει πάντα αποδεκτά αποτελέσματα
συμβολισμός Ο
δίνει ένα άνω φράγμα για την πολυπλοκότητα ενός αλγορίθμου
πολυωνυμικός αλγόριθμος
αλγόριθμος με πολυπλοκότητα φραγμένη από πάνω από πολυώνυμο, π.χ. O(n²)
εκθετικός αλγόριθμος
μη πολυωνυμικός αλγόριθμος, π.χ. τάξης O(2^n)
δυσχείριστο πρόβλημα
πρόβλημα χωρίς γνωστό αλγόριθμο πολυωνυμικού χρόνου, όπως του περιοδεύοντος πωλητή
ευριστικός αλγόριθμος
αλγόριθμος που στηρίζεται σε εμπειρική παρατήρηση ή τέχνασμα και μπορεί να πετύχει ή να αποτύχει
Είναι η εκτίμηση της επίδοσης ενός αλγορίθμου, κυρίως με τον αριθμό των βασικών πράξεων που εκτελεί στη χειρότερη περίπτωση ανάλογα με το μέγεθος της εισόδου. Έτσι συγκρίνουμε αλγορίθμους και διαλέγουμε τον αποδοτικότερο.
Γιατί δεν αρκεί να τρέξουμε ένα πρόγραμμα μερικές φορές για να πούμε ότι είναι σωστό;
Γιατί ένα σφάλμα μπορεί να φανεί μόνο με συγκεκριμένα δεδομένα. Στο παράδειγμα του βιβλίου με το ελάχιστο σε πίνακα 10 θέσεων χρειάζονται τουλάχιστον 7 εκτελέσεις για πιθανότητα περίπου 0,5 να βρεθεί το λάθος. Η ορθότητα θέλει απόδειξη.
Ποια είναι η πολυπλοκότητα της σειριακής και της δυαδικής αναζήτησης;
Η σειριακή αναζήτηση είναι Ο(n) και η δυαδική O(log n). Η ταξινόμηση ευθείας ανταλλαγής είναι Ο(n²), ενώ η ώθηση και η απώθηση σε στοίβα είναι Ο(1).
Ανοίγει το μενού κοινοποίησης του κινητού σου. Αν δεν υπάρχει, αντιγράφεται ο σύνδεσμος.
Νέα από το aporia.gr Νέες ενότητες και ό,τι βρίσκουμε στα θέματα των Πανελληνίων, στη σελίδα μας στο Facebook.