5.3 Πολυπλοκότητα αλγορίθμων

Ο απλούστερος τρόπος μέτρησης της επίδοσης ενός αλγορίθμου είναι ο εμπειρικός (empirical) ή αλλιώς ο λεγόμενος εκ των υστέρων (a posteriori). Δηλαδή, ο αλγόριθμος υλοποιείται και εφαρμόζεται σε ένα σύνολο δεδομένων, ώστε να υπολογισθεί ο απαιτούμενος χρόνος επεξεργασίας (proces sing time) και η χωρητικότητα μνήμης (memory space). Ο τρόπος όμως αυτός παρουσιάζει δύο κύρια μειονεκτήματα. - με τη μέθοδο αυτή είναι δύσκολο να προβλεφθεί η συμπεριφορά του αλγορίθμου για κάποιο άλλο σύνολο δεδομένων. - ο χρόνος επεξεργασίας εξαρτάται από το υλικό, τη γλώσσα προγραμματισμού και το μεταφραστή και προ πάντων από τη δεινότητα του προγραμματιστή.

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

Ο δεύτερος τρόπος εκτίμησης της επίδοσης ενός αλγορίθμου είναι ο θεωρητικός (theoretical) ή αλλιώς ο λεγόμενος εκ των προτέρων (a priori). Για το σκοπό αυτό εισάγεται μία μεταβλητή n, που εκφράζει το μέγεθος (size) του προβλήματος, ώστε η μέτρηση της αποδοτικότητας του αλγόριθμου να ισχύει για οποιοδήποτε σύνολο δεδομένων και ανεξάρτητα από υποκειμενικούς παράγοντες, όπως αυτοί που αναφέρθηκαν. Η σημασία της μεταβλητής αυτής εξαρτάται από το πρόβλημα, που πρόκειται να επιλυθεί. Για παράδειγμα, αν το πρόβλημα είναι η ταξινόμηση k στοιχείων τότε n=k. Στη συνέχεια ο χρόνος επεξεργασίας και ο απαιτούμενος χώρος μνήμης εκτιμώνται με τη βοήθεια μίας συνάρτησης f(n) που εκφράζει τη χρονική πολυπλοκότητα (time complexity) ή την πολυπλοκότητα χώρου (space complexity). Σε πολλές περιπτώσεις όμως δεν ενδιαφέρουν οι επακριβείς τιμές αλλά μόνο η γενική συμπεριφορά των αλγορίθμων, δηλαδή η τάξη του αλγορίθμου. Για το λόγο αυτό εισάγεται ο λεγόμενος συμβολισμός O (Ο-notation), όπου το Ο είναι το αρχικό γράμμα της αγγλικής λέξης order και διαβάζεται "όμικρον κεφαλαίο". Ακολουθεί όμως ένας τυπικός ορισμός.

Ορισμός: Αν η πολυπλοκότητα ενός αλγορίθμου είναι f(n), τότε λέγεται ότι είναι τάξης O(g(n)), αν υπάρχουν δύο θετικοί ακέραιοι c και n0, έτσι ώστε για κάθε nn0 να ισχύει: |f(n)| [pic] c|g(n)|

Παράδειγμα. Έστω ότι η πολυπλοκότητα ενός αλγορίθμου δίνεται από το πολυώνυμο [pic]. Ο πιο σημαντικός όρος του πολυωνύμου είναι η τρίτη δύναμη, αρκεί να σκεφτούμε ότι καθώς το x αυξάνεται (και τείνει στο άπειρο) ο όρος αυτός έχει μεγαλύτερο «ειδικό βάρος» και συνεχώς καθίσταται σημαντικότερος, ενώ η σημασία των υπολοίπων όρων σταδιακά μειώνεται. Επιπλέον, αγνοείται ο συντελεστής 2 της τρίτης δύναμης και έτσι προκύπτει ότι [pic]. Επομένως, τελικά η πολυπλοκότητα του αλγορίθμου είναι [pic]. Πλέον, η έκφραση αυτή εκφράζει την ποιοτική και όχι την ποσοτική συμπεριφορά του αλγορίθμου. Κατά τον ίδιο τρόπο αν δοθεί η έκφραση [pic], τότε προκύπτει ότι [pic], καθώς αγνοούνται οι μη σημαντικοί όροι του f(n) και ο συντελεστής 5 του όρου [pic]. Στο τελευταίο παράδειγμα είναι περισσότερο σαφές, γιατί αγνοούμε το δεύτερο και τρίτο όρο του f(n), αν απλά δώσουμε τιμές 1, 2, 3 κλπ στη μεταβλητή n και υπολογίσουμε το αποτέλεσμα του κάθε όρου της έκφρασης. Θα παρατηρήσουμε ότι πολύ σύντομα (λόγου χάριν, για n=10), το τελικό αποτέλεσμα της έκφρασης κατά βάση προέρχεται από τη δύναμη [pic].

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

Σχεδόν οι περισσότεροι αλγόριθμοι πρακτικού ενδιαφέροντος έχουν χρονική πολυπλοκότητα, που ανήκει σε μία από τις επόμενες κατηγορίες: - Ο(1). Κάθε εντολή του προγράμματος εκτελείται μία φορά ή το πολύ μερικές μόνο φορές. Στην περίπτωση αυτή λέγεται ότι ο αλγόριθμος είναι σταθερής πολυπλοκότητας. - Ο(logn). Ο αλγόριθμος είναι λογαριθμικής πολυπλοκότητας. Ας σημειωθεί ότι με "log" θα συμβολίζεται ο δυαδικός λογάριθμος, ενώ με "ln" θα συμβολίζεται ο φυσικός λογάριθμος. Συνήθως, οι λογάριθμοι που χρησιμοποιούνται στο βιβλίο αυτό είναι δυαδικοί. - O(n). Η πολυπλοκότητα λέγεται γραμμική. Αυτή είναι η καλύτερη επίδοση για έναν αλγόριθμο που πρέπει να εξετάσει ή να δώσει στην έξοδο n στοιχεία. - O(n logn). Διαβάζεται όπως ακριβώς γράφεται (n logn), δηλαδή χωρίς να χρησιμοποιείται κάποιο επίθετο (όπως για παράδειγμα γραμμολογαριθμική). Στην κατηγορία αυτή ανήκει μία πολύ σπουδαία οικογένεια αλγορίθμων ταξινόμησης. - O[pic]. Τετραγωνική πολυπλοκότητα. Πρέπει να χρησιμοποιείται μόνο για προβλήματα μικρού μεγέθους. - O[pic]. Κυβική πολυπλοκότητα. Και αυτοί οι αλγόριθμοι πρέπει να χρησιμοποιούνται μόνο για προβλήματα μικρού μεγέθους. - O[pic]. Σπάνια στην πράξη χρησιμοποιούνται αλγόριθμοι εκθετικής πολυπλοκότητας.

Στον πίνακα 5.3 υπολογίζεται ο χρόνος που απαιτείται από αλγορίθμους διαφόρων πολυωνυμικών και εκθετικών πολυπλοκοτήτων ως συνάρτηση του μεγέθους του προβλήματος (n). Βέβαια υποτίθεται ότι κάθε στοιχειώδης πράξη απαιτεί ένα μικροδευτερόλεπτο. Έτσι αν για έναν αλγόριθμο τάξης Ο[pic] διπλασιασθεί το μέγεθος του προβλήματος, τότε απαιτείται οκταπλάσιος (23) χρόνος για να περατωθεί ο αλγόριθμος. Επίσης διαπιστώνεται αμέσως ότι, οι αλγόριθμοι εκθετικής πολυπλοκότητας δεν είναι πρακτικής χρησιμότητας ακόμη και για μικρό αριθμό δεδομένων.

Πιν. 5.3. Χρόνοι εκτέλεσης αλγορίθμων ανάλογα με την πολυπλοκότητα και το μέγεθος Πολυπλοκότητα Μέγεθος προβλήματος αλγορίθμου n=20n=40 n=60 Ο(n) 0.00002 δεύτερα 0.00004 δεύτερα 0.00006 δεύτερα Ο[pic] 0.0004 δεύτερα 0.0016 δεύτερα 0.0036 δεύτερα Ο[pic] 0.008 δεύτερα0.064 δεύτερα 216 δεύτερα Ο[pic] 1.0 δεύτερo 2.7 ημέρες366 αιώνες Ο(n!) 771 αιώνες 3 1032 αιώνες3 1066 αιώνες

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