Κεφάλαιο 05.3 – Σελίδα 102 – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Ερωτήσεις - Θέματα για συζήτηση

Ερώτηση 9 (σελ. 102)

Να δοθεί ο ορισμός της πολυπλοκότητας αλγορίθμου.

Σκέψη / Μεθοδολογία: Το βιβλίο δεν δίνει μονολεκτικό τυπικό ορισμό στο εξαγόμενο κείμενο, αλλά τον εισάγει μέσα από τα παραδείγματα ταξινόμησης O(n²) και αναζήτησης O(n) — συνθέτουμε τον γενικό ορισμό από τη χρήση του συμβολισμού Ο σε αυτά τα παραδείγματα.

Λύση:

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

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

Πρόσεξε:

• Δεν υπάρχει μονολεκτικός ορισμός στο βιβλίο — αξιολογείται η σύνδεση με τον συμβολισμό Ο και το μέγεθος εισόδου n.

Ερώτηση 10 (σελ. 102)

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

Σκέψη / Μεθοδολογία: Δεδομένου ότι η λύση δίνεται σε γραπτή μορφή, αντικαθιστούμε το διάγραμμα με πίνακα τιμών για διαφορετικά n, που δείχνει την ίδια σχετική τάξη μεγέθους, και περιγράφουμε λεκτικά τη μορφή των τριών καμπυλών.

Λύση:

1. Υπολογίζουμε ενδεικτικές τιμές log₂(n), n και n² για n = 1, 10, 100, 1000.
2. Παρατηρούμε ότι η λογαριθμική καμπύλη ανεβαίνει πολύ αργά, η γραμμική ανεβαίνει με σταθερό ρυθμό, ενώ η τετραγωνική ανεβαίνει πολύ πιο απότομα καθώς μεγαλώνει το n.
3. Περιγράφουμε τη σχετική διάταξη: για μεγάλο n ισχύει πάντα log₂(n) < n < n².

Ενδεικτική απάντηση:

Πίνακας ενδεικτικών τιμών (αντί διαγράμματος):

Αν σχεδιάζαμε τις τρεις συναρτήσεις σε ένα διάγραμμα (άξονας x: το μέγεθος n, άξονας y: ο αριθμός πράξεων), η καμπύλη της λογαριθμικής πολυπλοκότητας Ο(log n) θα ήταν σχεδόν επίπεδη — αυξάνεται πολύ αργά ακόμη και για πολύ μεγάλα n. Η καμπύλη της γραμμικής πολυπλοκότητας Ο(n) θα ήταν ευθεία γραμμή με σταθερή κλίση. Η καμπύλη της τετραγωνικής πολυπλοκότητας Ο(n²) θα ανέβαινε πολύ πιο απότομα, ξεπερνώντας γρήγορα τις άλλες δύο καθώς μεγαλώνει το n. Γενικά ισχύει η σχέση Ο(log n) < Ο(n) < Ο(n²) για μεγάλα n, δηλαδή ο λογαριθμικός αλγόριθμος είναι ο πιο αποδοτικός και ο τετραγωνικός ο λιγότερο αποδοτικός από τους τρεις.

Πρόσεξε:

• Ζητείται διάγραμμα· εδώ αντικαθίσταται από πίνακα τιμών και λεκτική περιγραφή της μορφής των τριών καμπυλών.
• Η σειρά αποδοτικότητας είναι λογαριθμική > γραμμική > τετραγωνική (η λογαριθμική είναι η πιο αποδοτική).

Ερώτηση 11 (σελ. 102)

Ποια είναι η πολυπλοκότητα των λειτουργιών σε στοίβες και ουρές;

Σκέψη / Μεθοδολογία: Η ερώτηση συνδυάζει ύλη του Κεφαλαίου 3 (ορισμός στοίβας/ουράς) με την έννοια της πολυπλοκότητας του Κεφαλαίου 5. Οι βασικές λειτουργίες (ώθηση/απώθηση σε στοίβα, εισαγωγή/εξαγωγή σε ουρά) γίνονται πάντα στο ίδιο άκρο, χωρίς να χρειάζεται διάσχιση των υπόλοιπων στοιχείων.

Λύση:

1. Θυμόμαστε ότι η στοίβα λειτουργεί με λογική LIFO: οι λειτουργίες Εισαγωγή (push) και Εξαγωγή (pop) γίνονται πάντα στην κορυφή.
2. Θυμόμαστε ότι η ουρά λειτουργεί με λογική FIFO: η Εισαγωγή γίνεται στο ένα άκρο (ουρά) και η Εξαγωγή στο άλλο (αρχή).
3. Επειδή και στις δύο δομές η πρόσβαση γίνεται απευθείας σε συγκεκριμένη θέση (χωρίς αναζήτηση ή μετακίνηση άλλων στοιχείων), κάθε βασική λειτουργία εκτελείται σε σταθερό αριθμό βημάτων, ανεξάρτητο από το πλήθος n των στοιχείων.

Ενδεικτική απάντηση: Οι βασικές λειτουργίες τόσο της στοίβας (Εισαγωγή/push και Εξαγωγή/pop στην κορυφή) όσο και της ουράς (Εισαγωγή στο τέλος, Εξαγωγή από την αρχή) έχουν πολυπλοκότητα Ο(1) — σταθερού χρόνου. Αυτό συμβαίνει γιατί κάθε λειτουργία επενεργεί απευθείας σε συγκεκριμένη, γνωστή θέση (την κορυφή για τη στοίβα, τα δύο άκρα για την ουρά), χωρίς να χρειάζεται να διασχιστούν ή να μετακινηθούν τα υπόλοιπα στοιχεία της δομής, ανεξάρτητα από το πόσα στοιχεία n περιέχει αυτή τη στιγμή.

Πρόσεξε:

• Δεν εξετάζεται ρητά στο κείμενο του Κεφαλαίου 5 — η απάντηση συνδυάζει τον ορισμό στοίβας/ουράς του Κεφαλαίου 3 με την έννοια της πολυπλοκότητας.
• Να διευκρινιστεί ότι το Ο(1) αφορά τις βασικές λειτουργίες (push/pop, εισαγωγή/εξαγωγή), όχι π.χ. μια αναζήτηση μέσα στη δομή.

Ερώτηση 12 (σελ. 102)

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

Σκέψη / Μεθοδολογία: Άμεση ανάκληση του συμπεράσματος του §5.3.2: τόσο η επιτυχής όσο και η ανεπιτυχής σειριακή αναζήτηση έχουν πολυπλοκότητα Ο(n).

Λύση:

1. Ανατρέχουμε στο §5.3.2: η επιτυχής αναζήτηση έχει μέσο αριθμό συγκρίσεων E = (n+1)/2, άρα πολυπλοκότητα O(n).
2. Η ανεπιτυχής αναζήτηση εξετάζει όλα τα n στοιχεία, άρα είναι επίσης πολυπλοκότητας O(n).

Απάντηση: Η σειριακή (γραμμική) αναζήτηση έχει πολυπλοκότητα τάξης Ο(n), τόσο στην επιτυχή όσο και στην ανεπιτυχή περίπτωση — δηλαδή ο αριθμός των συγκρίσεων που χρειάζονται αυξάνεται γραμμικά με το πλήθος n των στοιχείων του πίνακα.

Πρόσεξε:

• Να αναφερθεί ότι ισχύει O(n) και για τις δύο περιπτώσεις (επιτυχής και ανεπιτυχής αναζήτηση).