απορία; ΟΤΑΝ ΕΧΕΙΣ ΑΠΟΡΙΑ

Ανάλυση Αλγορίθμων

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

Γ΄ Λυκείου · Πληροφορική · 15 λεπτά

Το μάθημα είναι στο σχολικό βιβλίο. Δεν το αντιγράφουμε εδώ. Άνοιξε το επίσημο κεφάλαιο και γύρνα για την εξάσκηση.

Άνοιγμα βιβλίου ↗

Η σύνοψη, οι όροι και οι ασκήσεις γράφτηκαν με τη βοήθεια τεχνητής νοημοσύνης από το σχολικό βιβλίο και μπορεί να έχουν λάθη. Πηγή είναι πάντα το βιβλίο: ό,τι σου φαίνεται περίεργο, έλεγξέ το εκεί. Βρήκες λάθος; Γράψε μας στο aporia@signmak.com.

Σχεδιάγραμμα

Δική μας σύνοψη της ενότητας, για επανάληψη. Πηγή είναι πάντα το βιβλίο.

Τι έγινε

  1. Η επίδοση ενός αλγορίθμου εκφράζεται με τον αριθμό των βασικών πράξεων (ανάθεση, σύγκριση, αριθμητική πράξη) στη χειρότερη περίπτωση, σε σχέση με το μέγεθος της εισόδου.
  2. Οι βρόχοι επανάληψης είναι το κρίσιμο σημείο: ο χρόνος εκτέλεσης μεγαλώνει με το πλήθος των επαναλήψεων n.
  3. Δύο προγράμματα συγκρίνονται σωστά μόνο με ίδια γλώσσα, ίδιο μεταφραστή, ίδια υπολογιστική πλατφόρμα και ίδια δεδομένα.
  4. Οι δοκιμαστικές εκτελέσεις δεν εγγυώνται ορθότητα· η απόδειξη πρέπει να δείχνει ότι ο αλγόριθμος τερματίζει και δίνει αποδεκτά αποτελέσματα.
  5. Η εκ των υστέρων μέτρηση εξαρτάται από υλικό και προγραμματιστή, γι' αυτό χρησιμοποιείται η εκ των προτέρων εκτίμηση με τον συμβολισμό Ο.
  6. Κύριες τάξεις πολυπλοκότητας: Ο(1), O(log n), O(n), O(n log n), O(n²), O(n³) και Ο(2^n), που σπάνια χρησιμοποιείται στην πράξη.
  7. Είδη αλγορίθμων: παράλληλοι, πολυωνυμικοί και εκθετικοί· για δυσχείριστα προβλήματα χρησιμοποιούνται προσεγγιστικοί και ευριστικοί αλγόριθμοι.

Όροι

χειρότερη περίπτωση
οι είσοδοι που οδηγούν τον αλγόριθμο στον μέγιστο αριθμό βασικών πράξεων
μέγεθος εισόδου
τα δεδομένα που δίνονται στον αλγόριθμο, π.χ. το πλήθος των στοιχείων προς ταξινόμηση
βασική πράξη
ανάθεση τιμής, σύγκριση ή αριθμητική πράξη μεταξύ δύο μεταβλητών
αποδοτικότητα
ένας αλγόριθμος είναι αποδοτικότερος αν δίνει το ίδιο αποτέλεσμα σε λιγότερο χρόνο ή με λιγότερη μνήμη
ορθότητα
η απόδειξη ότι ο αλγόριθμος τερματίζει και δίνει πάντα αποδεκτά αποτελέσματα
συμβολισμός Ο
δίνει ένα άνω φράγμα για την πολυπλοκότητα ενός αλγορίθμου
πολυωνυμικός αλγόριθμος
αλγόριθμος με πολυπλοκότητα φραγμένη από πάνω από πολυώνυμο, π.χ. O(n²)
εκθετικός αλγόριθμος
μη πολυωνυμικός αλγόριθμος, π.χ. τάξης O(2^n)
δυσχείριστο πρόβλημα
πρόβλημα χωρίς γνωστό αλγόριθμο πολυωνυμικού χρόνου, όπως του περιοδεύοντος πωλητή
ευριστικός αλγόριθμος
αλγόριθμος που στηρίζεται σε εμπειρική παρατήρηση ή τέχνασμα και μπορεί να πετύχει ή να αποτύχει

Εξάσκηση

Συχνές απορίες

Τι είναι η ανάλυση αλγορίθμων;

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

Γιατί δεν αρκεί να τρέξουμε ένα πρόγραμμα μερικές φορές για να πούμε ότι είναι σωστό;

Γιατί ένα σφάλμα μπορεί να φανεί μόνο με συγκεκριμένα δεδομένα. Στο παράδειγμα του βιβλίου με το ελάχιστο σε πίνακα 10 θέσεων χρειάζονται τουλάχιστον 7 εκτελέσεις για πιθανότητα περίπου 0,5 να βρεθεί το λάθος. Η ορθότητα θέλει απόδειξη.

Ποια είναι η πολυπλοκότητα της σειριακής και της δυαδικής αναζήτησης;

Η σειριακή αναζήτηση είναι Ο(n) και η δυαδική O(log n). Η ταξινόμηση ευθείας ανταλλαγής είναι Ο(n²), ενώ η ώθηση και η απώθηση σε στοίβα είναι Ο(1).

Ανοίγει το μενού κοινοποίησης του κινητού σου. Αν δεν υπάρχει, αντιγράφεται ο σύνδεσμος.

Είσαι εκπαιδευτικός; Ανάρτησέ το στο Google Classroom ↗

Νέα από το aporia.gr Νέες ενότητες και ό,τι βρίσκουμε στα θέματα των Πανελληνίων, στη σελίδα μας στο Facebook.