Κεφάλαιο 1Εισαγωγή

Ένας τυπικός ορισμός της έννοιας του αλγορίθμου είναι ο εξής:

Ορισμός.
Αλγόριθμος είναι ένα πεπερασμένο σύνολο εντολών, αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, οι οποίες όταν ακολουθηθούν επιτυγχάνεται ένα επιθυμητό αποτέλεσμα ή επιλύεται ένα συγκεκριμένο πρόβλημα. $\mathrm{\square }$  

Επιπροσθέτως, μία ακολουθία εντολών πρέπει να ικανοποιεί τα ακόλουθα κριτήρια, ώστε να θεωρείται αλγόριθμος:

1. 1.

   Είσοδος (input). Καμία, μία ή περισσότερες ποσότητες να δίνονται ως είσοδοι στον αλγόριθμο.

2. 2.

   Έξοδος (output). Ο αλγόριθμος να δημιουργεί τουλάχιστον μία ποσότητα ως αποτέλεσμα.

3. 3.

   Καθοριστικότητα (definiteness). Κάθε εντολή να καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσής της.

4. 4.

   Περατότητα (finiteness). Ο αλγόριθμος να τελειώνει μετά από πεπερασμένα βήματα εκτέλεσης των εντολών του. Μία διαδικασία που δεν τελειώνει μετά από ένα πεπερασμένο αριθμό βημάτων λέγεται απλώς υπολογιστική διαδικασία (computational procedure).

5. 5.

   Αποτελεσματικότητα (effectiveness). Κάθε μεμονωμένη εντολή του αλγορίθμου να είναι επαρκώς απλή, έτσι ώστε να μπορεί να εκτελεστεί από ένα άτομο με χρήση χαρτιού και μολυβιού. Δεν αρκεί δηλαδή να είναι ορισμένη (κριτήριο 3), αλλά πρέπει να είναι και εκτελέσιμη.

Από τον Niklaus Wirth (που παρουσίασε την πρώτη δομημένη γλώσσα προγραμματισμού, την Pascal) διατυπώθηκε το 1976 η εξής εξίσωση:

Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα

(1.1)

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

Ένα άλλο σχόλιο που προκύπτει παρατηρώντας την Εξίσωση 1.1 είναι ότι η έννοια του αλγόριθμου δεν ταυτίζεται με την έννοια του προγράμματος. Το δεύτερο είναι μία υλοποίηση του πρώτου με τη βοήθεια των εντολών και των εργαλείων ενός προγραμματιστικού περιβάλλοντος. Σε σχέση με τα ανωτέρω κριτήρια, ένα πρόγραμμα δεν ικανοποιεί αναγκαστικά το 4ο κριτήριο της περατότητας (για παράδειγμα, ένα λειτουργικό σύστημα εκτελεί διαρκώς έναν ατέρμονα βρόχο περιμένοντας εντολές να εισέλθουν στο σύστημα). Στο βιβλίο αυτό θα ασχοληθούμε με αλγορίθμους που πληρούν το κριτήριο αυτό, δηλαδή τερματίζουν πάντοτε.

Λόγω της σπουδαιότητας του αντικειμένου και της κεντρικότητας τους στην επιστήμη, η Πληροφορική συχνά ορίζεται ως η επιστήμη που μελετά τους αλγορίθμους από τη σκοπιά:

1. 1.

   του υλικού. Οι διάφορες τεχνολογίες υλικού επηρεάζουν την αποδοτικότητα ενός αλγορίθμου (όπως π.χ. στον τομέα της σχεδίασης ολοκληρωμένων κυκλωμάτων VLSI).

2. 2.

   των γλωσσών προγραμματισμού. Το είδος της γλώσσας προγραμματισμού που χρησιμοποιείται (χαμηλού ή υψηλού επιπέδου) αλλάζει τη μορφή και τον αριθμό των εντολών ενός αλγορίθμου (σε γλώσσα assembly π.χ. η υλοποίηση των δομών επανάληψης γίνεται με χρήση της εντολής διακλάδωσης $\mathrm{–}$ jump).

3. 3.

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

4. 4.

   την αναλυτική σκοπιά. Μελετώνται οι υπολογιστικοί πόροι (computer resources) που χρησιμοποιούνται από έναν αλγόριθμο, όπως το μέγεθος της κύριας και της δευτερεύουσας μνήμης, ο χρόνος για CPU και για Ι/Ο κλπ. Το αντικείμενο αυτό θα εξηγηθεί πληρέστερα στη συνέχεια.

Προφανώς εμείς στα πλαίσια αυτού του μαθήματος θα σταθούμε στην τελευταία οπτική γωνία.

Τέλος, για να ολοκληρώσουμε αυτά που πρέπει να θυμηθούμε και να περάσουμε σε νέα θέματα, πρέπει να αναφέρουμε και τους τρόπους παρουσίασης των αλγορίθμων, οι οποίοι είναι οι εξής τρείς:

1. 1.

   με την περιγραφή του αλγόριθμου σε φυσική γλώσσα (natural language) ή με ελεύθερο κείμενο (free text). Στο συγκεκριμένο τρόπο παρουσίασης χρειάζεται προσοχή γιατί μπορεί να παραβιασθεί το τρίτο κριτήριο του ορισμού.

2. 2.

   με τη χρήση ενός διαγράμματος ροής (flow chart).

3. 3.

   με κωδικοποίηση (coding), δηλαδή με ένα πρόγραμμα που, όταν εκτελεσθεί, θα δώσει τα ίδια αποτελέσματα με τον αλγόριθμο.

Τα διαγράμματα ροής χρησιμοποιούνταν εκτεταμένα στο παρελθόν για την αλγοριθμική περιγραφή προβλημάτων. Ωστόσο, σήμερα έχουν εγκαταλειφθεί διότι: (α) δεν πληρούν μία σημαντική ιδιότητα του προγραμματισμού, δηλαδή δεν είναι δομημένα, και (β) δεν είναι λειτουργικά για σύνθετα προβλήματα. Οι αλγόριθμοι του βιβλίου αυτού είναι κωδικοποιημένοι είτε σε ψευδογλώσσα, είτε σε γλώσσα προγραμματισμού (όπως C/C++), αλλά είναι αυτονόητο ότι πολύ εύκολα μπορούν να διατυπωθούν σε οποιαδήποτε γλώσσα προγραμματισμού.

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

      function russe(Χ,Υ)
1.    Α[1] <-- Χ; Β[1] <-- Υ;
2.    i <-- 1;
3.    while Α[i]>1 do
4.       Α[i+1] <-- Α[i] div 2;
5.       Β[i+1] <-- Β[i]+Β[i];
6.       i <-- i+1;
7.    prod <-- 0;
8.    while i>0 do
9.       if (Α[i] div 2=1) then prod <-- prod+B[i];
10.      i <-- i-1;
11.   return prod;

Ο αλγόριθμος αυτός δέχεται στην είσοδο δύο ακεραίους αριθμούς Χ και Υ, τους οποίους καταχωρίζει στις πρώτες θέσεις δύο πινάκων Α και Β αντίστοιχα (εντολές σειράς 1). Στις επόμενες θέσεις του πίνακα Α καταχωρίζει το ακέραιο πηλίκο της διαίρεσης του περιεχομένου της προηγούμενης θέσης δια του δύο (στην εντολή 4), ενώ στον πίνακα Β καταχωρίζει δύο φορές το περιεχόμενο της προηγούμενης θέσης του ίδιου πίνακα (εντολή 5). Τέλος, με τη βοήθεια της μεταβλητής prod αθροίζει τα περιεχόμενα των θέσεων του πίνακα Β, όταν το περιεχόμενο των αντίστοιχων θέσεων του πίνακα Α είναι περιττό (εντολές 8-11).

Σε πρώτη ανάγνωση δεν είναι εύκολο να γίνει αντιληπτός ο σκοπός του αλγορίθμου αυτού. Ας εξετάσουμε ένα πρακτικό παράδειγμα, για να καταλάβουμε το μηχανισμό του. Έστω ότι δίνονται οι αριθμοί 35 και 29. Το περιεχόμενο των δύο πινάκων και η τιμή της μεταβλητής prod διαδοχικά παρουσιάζονται στo Σχήμα 1.1.

                      X    Y   prod
              i=1    35    29    29
              i=2    17    58    58
        i=3     8   116
        i=4     4   232
        i=5     2   464
              i=6     1   928   928
                               -----
                               1015

Μπορούμε πολύ εύκολα να διαπιστώσουμε ότι η τελική τιμή (δηλαδή, το 1015) της μεταβλητής prod ισούται με το αποτέλεσμα του πολλαπλασιασμού 35x29. Σε επιβεβαίωση, λοιπόν, αυτού που διατυπώθηκε προηγουμένως (δηλαδή, ότι για την επίλυση κάποιου προβλήματος μπορούν να προταθούν περισσότεροι του ενός αλγόριθμοι) η συνάρτηση russe είναι ένας εναλλακτικός τρόπος για την εκτέλεση του πολλαπλασιασμού σε σχέση με την τεχνική που έχουμε διδαχθεί στο δημοτικό σχολείο. Ο τρόπος αυτός αναφέρεται σε πολλές πηγές της βιβλιογραφίας ως «πολλαπλασιασμός αλά ρωσικά» γιατί κατά την παράδοση εφαρμόζονταν στη ρωσική ύπαιθρο στο παρελθόν, αν και η πατρό/μητρότητά του διεκδικείται από πολλούς.

Αξίζει να σημειωθεί ότι αυτός ο τρόπος πολλαπλασιασμού ακεραίων είναι η βάση του αλγορίθμου που πρακτικά χρησιμοποιείται σε επίπεδο κυκλωμάτων του υπολογιστή, γιατί είναι ταχύτερος από αυτόν που γνωρίζουμε. Ο λόγος της ταχύτητάς του είναι ότι στην ουσία δεν εκτελεί πολλαπλασιασμούς αλλά προσθέσεις και πράξεις ολίσθησης που γίνονται εύκολα σε χαμηλό επίπεδο (όπως, για παράδειγμα, σε γλώσσα C/C++).

Όπως αναφέρθηκε, στις σημειώσεις αυτές θα παρουσιάσουμε τους αλγορίθμους τόσο με ψευδοκώδικα όσο και κάποια συγκεκριμένη γλώσσα προγραμματισμού. Ωστόσο, πρέπει η διαφορά μεταξύ αλγορίθμου και προγράμματος να είναι σαφής: ο πρώτος είναι γενικότερος, το δεύτερο είναι ειδικότερο του πρώτου. Αυτό γίνεται κατανοητό αν θεωρήσουμε τα όρια του υλικού. Για παράδειγμα, ένας ακέραιος αποθηκεύεται σε 4 χαρακτήρες και επομένως μπορεί να πάρει τιμές από -65.000 μέχρι 65.000. Επομένως, δεν μπορούμε να εφαρμόσουμε τον αλγόριθμο «αλά ρωσικά» για πολλαπλασιασμό ακεραίων με τιμές εκτός αυτών των ορίων, αλλά ακόμη και για πολλαπλασιασμό ακεραίων που είναι μεν εντός των ανωτέρω ορίων αλλά δεν είναι το γινόμενό τους. Καταλήγουμε στο συμπέρασμα ότι για κάθε αλγόριθμο πρέπει να προσδιορίζουμε και το αντίστοιχο πεδίο ορισμού (domain of definition).

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

Όπως αναφέραμε, συνήθως σε κάποιο δεδομένο πρόβλημα μπορούμε να εφεύρουμε πολλές εναλλακτικές λύσεις. Είναι αναγκαία, επομένως, η αξιολογική κατάταξη των εναλλακτικών λύσεων, ώστε να επιλεγεί η προσφορότερη. Μιλώντας με τεχνικούς όρους, σκοπός μας είναι να προσδιορίσουμε την επίδοση (performance) ή την αποδοτικότητα (efficiency) του κάθε αλγορίθμου. Τα βασικά κριτήρια για την επιλογή ενός αλγορίθμου είναι οι απαιτήσεις του σε υπολογιστικούς πόρους, δηλαδή:

• •

  ο απαιτούμενος χρόνος εκτέλεσης και

• •

  ο απαιτούμενος χώρος αποθήκευσης.

Καθώς πλέον η μνήμες (κύριες και δευτερεύουσες) γίνονται συνεχώς μεγαλύτερες και φθηνότερες, ο απαιτούμενος χρόνος εκτέλεσης είναι τελικά το σημαντικότερο κριτήριο. Άλλα κριτήρια, όπως η δικτυακή χωρητικότητα, ο αριθμός των πυλών, το πλήθος μηνυμάτων και άλλα, είναι μεγάλης σημασίας για συγκεκριμένες περιπτώσεις.

Υπάρχουν δύο τρόποι για να εξετάσουμε την επίδοση ενός αλγορίθμου:

• •

  ο πρακτικός ή εκ των υστέρων (a posteriori) και

• •

  ο θεωρητικός ή εκ των προτέρων (a priori).

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

• •

  το χρησιμοποιούμενο υλικό, δηλαδή τα συγκεκριμένα χαρακτηριστικά του υπολογιστή, όπως ταχύτητα του επεξεργαστή, το μέγεθος της κύριας ή της δευτερεύουσας μνήμης, τη χρήση κρυφής μνήμης (cache) κοκ.

• •

  τη χρησιμοποιούμενη γλώσσα προγραμματισμού, καθώς είναι γνωστό ότι υπάρχουν ταχύτερες και βραδύτερες γλώσσες με περισσότερη ή λιγότερη πρόσβαση στο φυσικό επίπεδο (όπως για παράδειγμα οι παλαιότερες γλώσσες σε αντίθεση με τις νεότερες C/C++).

• •

  το χρησιμοποιούμενο μεταγλωττιστή/ερμηνευτή, καθώς είναι δυνατόν να υπάρχουν διαθέσιμοι εμπορικά (ή και δωρεάν μέσα από το διαδίκτυο) περισσότεροι του ενός μεταγλωττιστές που μάλιστα μπορεί να τρέχουν σε διαφορετικά λειτουργικά συστήματα (όπως για παράδειγμα, Unix, Linux, Windows κοκ).

• •

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

• •

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

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

Μία βασική παράμετρος για τη θεωρητική ανάλυση είναι το μέγεθος του προβλήματος (problem size). Για παράδειγμα, στην περίπτωση της ταξινόμησης $n$ αριθμών, του πολλαπλασιασμού δύο τετραγωνικών πινάκων $n\times n$ ή της διάσχισης ενός δένδρου με $n$ κόμβους, λέγεται ότι το μέγεθος του προβλήματος είναι $n$. Είναι δυνατόν το μέγεθος ενός προβλήματος να εκφράζεται με δύο αριθμούς αντί για έναν. Για παράδειγμα, ένας γράφος διακρίνεται από το πλήθος των κορυφών $n$ αλλά και το πλήθος των ακμών $m$.

Δεδομένου, λοιπόν, ενός προβλήματος και ενός ή περισσοτέρων αλγορίθμων για την επίλυση του, σκοπός μας είναι η εύρεση της χρονικής πολυπλοκότητας (time complexity) και της χωρικής πολυπλοκότητας (space complexity) τους ως συνάρτησης του $n$. Την πολυπλοκότητα εκφράζουμε με τη βοήθεια ειδικών συμβολισμών (notation), που ίσως γνωρίζουμε από τα μαθήματα των προηγουμένων εξαμήνων. Αυτοί οι συμβολισμοί είναι: Ο, Ω, Θ, ο και ω, και εξ αυτών οι σπουδαιότεροι και συχνότερα χρησιμοποιούμενοι είναι οι τρεις πρώτοι. Η έννοια της πολυπλοκότητας και οι έννοιες των συμβολισμών είναι τεχνικές και για το λόγο αυτό πρέπει να ορισθούν προσεκτικά στο Κεφάλαιο 2.

Πριν από οποιαδήποτε αναφορά σε ανάλυση αλγορίθμων, είναι αναγκαίο να μελετήσουμε τα μοντέλα υπολογισμού στα οποία εκτελούνται οι αλγόριθμοί μας. Τα μοντέλα που θα εξετάσουμε είναι: (α) η Μηχανή Τυχαίας Προσπέλασης (Random Access Machine - RAM) και (β) η Mηχανή Δεικτών (Pointer Machine - PM).

Μια υπολογιστική μηχανή με βάση το μοντέλο RAM έχει τα εξής χαρακτηριστικά:

• •

  έχει 1 επεξεργαστή, 4 καταχωρητές, 1 συσσωρευτή , 3 καταχωρητές δείκτη (index registers) και ένα άπειρο πλήθος θέσεων μνήμης, οι οποίες είναι αριθμημένες από το 0.

• •

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

• •

  οι εντολές είναι μονής διεύθυνσης (one-address), δηλαδή κάθε εντολή αναφέρεται μόνο σε μια θέση μνήμης.

Το μοντέλο της μηχανής RAM ανταποκρίνεται στη δομή των σύγχρονων υπολογιστών και θεωρεί ότι οι εντολές του αλγορίθμου μας εκτελούνται η μία μετά την άλλη και όχι ταυτόχρονα. Κάθε εντολή περιλαμβάνει την εκτέλεση βασικών πράξεων σε δύο τιμές (όπως χαρακτήρες, ακεραίους κλπ) που είναι αποθηκευμένες στη μνήμη του υπολογιστή. Σημειώνεται ότι υπάρχει και το μοντέλο της Παράλληλης Μηχανής Τυχαίας Προσπέλασης (Parallel Random Access Machine - PRAM), όπου θεωρείται ότι υπάρχουν πολλοί επεξεργαστές, οπότε είναι δυνατόν εντολές περισσότερες της μίας να εκτελούνται ταυτόχρονα. Το μοντέλο PRAM δεν θα μας απασχολήσει στη συνέχεια.

Το μοντέλο PM παρουσιάζει τα ίδια χαρακτηριστικά με το μοντέλο RAM με τη διαφορά ότι δεν επιτρέπει την προσπέλαση με υπολογισμό διεύθυνσης. Προσπέλαση σε δεδομένη διεύθυνση είναι δυνατή μόνο αν υπάρχει δείκτης σε αυτή τη διεύθυνση. Το μοντέλο PM είναι ασθενέστερο του RAM. Όμως, οι αλγόριθμοι που αναπτύσσονται σε PM είναι συχνά κομψότεροι, ενώ παρέχουν ταυτόχρονα διαίσθηση για την εγγενή δυσκολία του προβλήματος.

Για να εκφράσουμε την αποτελεσματικότητα ενός αλγορίθμου (με βάση το μοντέλο RAM) πρέπει να εκτιμήσουμε το κόστος εκτέλεσης κάθε πράξης ή/και κάθε εντολής, να υπολογίσουμε πόσες φορές θα εκτελεσθεί κάθε εντολή και να αθροίσουμε τα επί μέρους κόστη ώστε να βρούμε το συνολικό κόστος. Αρχικά ας θεωρήσουμε το κόστος των πράξεων.

Ένα πρόγραμμα ή ένας αλγόριθμος μπορεί να αποτελείται από πολλών ειδών πράξεις, όπως: αριθμητικές πράξεις (πρόσθεση, αφαίρεση, πολλαπλασιασμός, διαίρεση, πράξη modulo), λογικές (boolean) πράξεις, συγκρίσεις (εντολές if, for, while, repeat until), καταχωρίσεις (assignment) κοκ. Όλες αυτές τις πράξεις ονομάζουμε στοιχειώδεις (elementary). Απαραίτητη προϋπόθεση για να θεωρηθεί μία πράξη ως στοιχειώδης είναι να απαιτεί χρόνο εκτέλεσης φραγμένο από επάνω από μία σταθερά που να εξαρτάται μόνο από το συγκεκριμένο περιβάλλον υλοποίησης (όπως το χρησιμοποιούμενο μηχάνημα, τη γλώσσα προγραμματισμού, το μεταγλωττιστή, κλπ). Στην πράξη είναι γνωστό ότι αυτές οι στοιχειώδεις πράξεις που αναφέρθηκαν δεν έχουν το ίδιο χρονικό κόστος εκτέλεσης. Για παράδειγμα, η πράξη του πολλαπλασιασμού είναι πιο χρονοβόρα από την πράξη της πρόσθεσης. Ωστόσο, για λόγους ευκολίας θεωρούμε ότι όλες οι στοιχειώδεις πράξεις έχουν μοναδιαίο κόστος (unit cost).

Χρειάζεται προσοχή, ώστε να μην παρεξηγηθεί αυτή η έννοια του μοναδιαίου κόστους. Για παράδειγμα, η εντολή for i <-- 1 to n do ή η εντολή x <-- n! αποτελούνται από πολλές απλούστερες πράξεις που πρέπει όλες να καταμετρηθούν. Πιο συγκεκριμένα, στην πρώτη περίπτωση υπεισέρχεται ένα πλήθος προσθέσεων, συγκρίσεων και καταχωρίσεων, ενώ στη δεύτερη περίπτωση υπεισέρχεται αντίστοιχα ένα πλήθος πολλαπλασιασμών, συγκρίσεων και καταχωρίσεων.

Όλα τα ανωτέρω ισχύουν με την προϋπόθεση ότι το περιεχόμενο κάθε μεταβλητής χωρά σε μια θέση μνήμης. Για παράδειγμα, είναι γνωστό ότι ισχύει 8!=40.320 αλλά 9!=362.880, αριθμός που υπερβαίνει τα όρια του απλού ακεραίου. Το ίδιο πρόβλημα μπορεί να προκύψει κατά τον υπολογισμό των αριθμών Fibonacci, σύμφωνα με τον επόμενο αλγόριθμο (θεωρώντας το $n\ge 0$ ακέραιο αριθμό).

      function fib(n)
 1.   i <-- 1; j <-- 0;
 2.   for k <-- 1 to n do
 3.      j <-- i+j;
 4.      i <-- j-1;
 5.   return j;

Αν, λοιπόν, χρησιμοποιήσουμε αυτό το απλούστατο ψευδοκώδικα για τον υπολογισμό του $F_{47}$, τότε θα προκύψει υπερχείλιση, ενώ για την καταχώριση του αριθμού $F_{65535}$ απαιτούνται 45.496 bits. Άρα, όταν τα περιεχόμενα των μεταβλητών δεν χωρούν σε μια θέση μνήμης, τότε οι πράξεις στοιχίζουν όσο και το μήκος των δεδομένων, δηλαδή για τον ακέραιο $n$ κάθε πράξη στοιχίζει $\lfloor \log n\rfloor +1$. Το μοντέλο μηχανής που βασίζεται σε αυτή την υπόθεση εργασίας ονομάζεται RAM λογαριθμικού κόστους (logarithmic cost) και θα εξετασθεί στο Κεφάλαιο 5.

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

Η οπτική γωνία έκφρασης της επίδοσης ενός αλγορίθμου εκτιμώντας και αθροίζοντας τα επί μέρους κόστη των πράξεων χρησιμοποιήθηκε σε μεγάλη έκταση από τον Donald Knuth στο τρίτομο ιστορικό του βιβλίο «The Art of Computer Programming», το οποίο εκδόθηκε τη δεκαετία του 70. Η προσέγγιση αυτή είναι η λεπτομερέστερη και ακριβέστερη αλλά και η πλέον επίπονη. Αν και η θεώρηση του κόστους των πράξεων βοηθά στην κατανόηση των επί μέρους παραγόντων κόστους και τελικά στη μείωση του συνολικού κόστους, εν τούτοις δεν χρησιμοποιείται στη βιβλιογραφία καθώς έχει επικρατήσει μία μακροσκοπικότερη προσέγγιση που εξετάζει το κόστος των εντολών.

Για να εκφράσουμε την πολυπλοκότητα ενός αλγορίθμου λαμβάνοντας υπ’ όψιν το κόστος των εντολών (και με βάση το μοντέλο RAM), πρέπει να εκτιμήσουμε το κόστος εκτέλεσης κάθε εντολής, να υπολογίσουμε το πλήθος εκτελέσεων κάθε εντολής και να αθροίσουμε τα επί μέρους κόστη, ώστε να βρούμε το συνολικό κόστος. Και πάλι είναι ευνόητο ότι το κόστος κάθε εντολής μπορεί να είναι διαφορετικό. Για παράδειγμα, από τη συνάρτηση russe αξίζει να προσέξουμε τις τρεις εντολές: i <-- 1 (εντολή 3), X[i+1] <-- X[i] div 2 (εντολή 5) και if X[i] is odd then prod <-- prod+Y[1] (εντολή 10), ώστε να διαπιστώσουμε αμέσως την αλήθεια της πρότασης αυτής. Για το λόγο αυτό θεωρούμε ότι η $i$-οστή εντολή ενός αλγορίθμου έχει ένα σταθερό κόστος $c_i$ που είναι φραγμένο από επάνω για οποιοδήποτε περιβάλλον υλοποίησης.

Στη συνέχεια θα εξετάσουμε την προηγούμενη κοστολόγηση εντολών σε ένα λεπτομερές πρόγραμμα (κατ’εξαίρεση και όχι σε έναν απλό αλγόριθμο). Δηλαδή, θα εφαρμόσουμε μία επακριβή (exact) ανάλυση σε ένα πρόγραμμα C υπολογίζοντας το κόστος εκτέλεσης γραμμή-γραμμή σε συνδυασμό με το πλήθος των εκτελέσεων της κάθε γραμμής. Το πρόγραμμα που θα δοκιμάσουμε υλοποιεί την ταξινόμηση επιλογής, που γνωρίζουμε από το μάθημα των Δομών Δεδομένων. Ένα παράδειγμα εκτέλεσης του αλγορίθμου, βρίσκεται στο Σχήμα 1.2.

     procedure select
1.   for (i=0; i<n; ++i) {
2.      min=i;
3.      for (j=i+1; j<=n; ++j)
4.         if (A[j]<A[min]) min=j;
5.      temp=A[i];
6.      A[i]=A[min];
7.      A[min]=temp;
8.   }

Ο Πίνακας 1.1 δίνει για κάθε γραμμή το κόστος της γραμμής και τον αντίστοιχο αριθμό επαναλήψεων. Για να βρούμε τη συνολική επίδοση του προγράμματος, αθροίζουμε τα επιμέρους κόστη και έχουμε:

	$T(n)$	$=$	$c_1(n+1)+c_{2}n+c_3{\displaystyle \sum _{j=1}^n}j+c_4{\displaystyle \sum _{j=1}^n}(j-1)+c_{5}n+c_{6}n+c_{7}n$
		$=$	$c_{1}n+c_1+c_{2}n+c_3{\displaystyle \frac{n(n+1)}{2}}+c_4{\displaystyle \frac{n(n+1)}{2}}-c_{4}n+c_{5}n+c_{6}n+c_{7}n$
		$=$	$(c_3/2+c_4/2)n^2+(c_1+c_2+c_3/2-c_4/2+c_5+c_6+c_7)n+c_1$
		$=$	$a{n}^2+bn+c$

Παρατηρούμε ότι το τελικό κόστος είναι μία τετραγωνική συνάρτηση και ότι εξαρτάται από το μέγεθος της εισόδου, δηλαδή το $n$, και όχι από το είδος της εισόδου, αλλά κυρίως δεν εξαρτάται ασυμπτωτικά από συγκεκριμένες τιμές των κοστών $c_i$. Στη συνέχεια θα εφαρμόσουμε την ίδια τεχνική για το πρόγραμμα σε C της ταξινόμηση με εισαγωγή, που επίσης γνωρίζουμε από το μάθημα των Δομών Δεδομένων.

     procedure insert
1.   for(j=2; j<=n; ++j) {
2.      key=A[j];
3.      i=j-1;
4.      while (i>0 && A[i]>key)
5.         A[i+1]=A[i]
6.         i=i-1;
7.      A[i+1]=key
8.   }

Όπως προηγουμένως, στον Πίνακα 1.2 παρουσιάζονται τα αντίστοιχα κόστη ανά γραμμή. Στον πίνακα αυτόν με $t_j$ συμβολίζεται το πλήθος των εκτελέσεων του βρόχου while για τις διάφορες τιμές του j. Όπως προηγουμένως, για να βρούμε το συνολικό κόστος του προγράμματος αθροίζουμε τα επί μέρους κόστη και έχουμε:

	$T(n)$	$=$	$c_{1}n+c_2(n-1)+c_3(n-1)+c_4{\displaystyle \sum _{j=2}^n}{t}_j+c_5{\displaystyle \sum _{j=2}^n}(t_j-1)+$
			$c_6{\displaystyle \sum _{j=2}^n}(t_j-1)+c_7(n-1)$
		$=$	$(c_4+c_5+c_6){\displaystyle \sum _{j=2}^n}{t}_j+(c_1+c_2+c_3-c_5-c_6+c_7)n$
			$+(-c2-c3+c5+c6-c7)$

Επομένως, για να επιλυθεί περαιτέρω η εξίσωση $T(n)$, πρέπει να εστιάσουμε στην τιμή της μεταβλητής $t_j$. Αν ο πίνακας είναι ήδη ταξινομημένος, τότε ισχύει $t_j=1$, οπότε με εύκολη άλγεβρα καταλήγουμε ότι η συνάρτηση $T(n)$ είναι γραμμική. Αυτή είναι η καλύτερη δυνατή περίπτωση. H χειρότερη περίπτωση συμβαίνει όταν θέλουμε να ταξινομήσουμε κατά αύξουσα σειρά, αλλά τα στοιχεία εισέρχονται στην είσοδο κατά φθίνουσα σειρά. Τότε ισχύει $t_j=j$, οπότε και πάλι με εύκολη άλγεβρα καταλήγουμε ότι η συνάρτηση $T(n)$ είναι τετραγωνική. Η μέση περίπτωση εξαρτάται από την κατανομή των στοιχείων και τις μεταξύ τους σχέσεις και είναι δυσκολότερο να βρεθεί επακριβώς. Επί του παρόντος, ας αρκεσθούμε στη διαβεβαίωση ότι και στην περίπτωση αυτή η αντίστοιχη $T(n)$ είναι τετραγωνική συνάρτηση.

Όπως και στο προηγούμενο παράδειγμα, καταλήγουμε και τώρα στο απλό συμπέρασμα ότι το συνολικό κόστος δεν εξαρτάται από τις τιμές των επί μέρους κοστών $c_i$ καθώς αυτά εμφανίζονται στους σταθερούς συντελεστές και δεν επηρεάζουν την ασυμπτωτική συμπεριφορά του αλγορίθμου/προγράμματος, κάτι που ισχύει για το μέγεθος του προβλήματος $n$. Επομένως, συμπεραίνουμε ότι ο τρόπος αυτός κοστολόγησης, αν και επακριβής, είναι υπερβολικός και τελικά μη πρακτικός. Προκειμένου, λοιπόν, να εκτιμήσουμε την επίδοση ενός αλγορίθμου, πρέπει να απλοποιήσουμε την κατάσταση ακόμη περισσότερο και να εστιάσουμε στα κρίσιμα σημεία του αλγορίθμου.

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

Ας θεωρήσουμε την επόμενη εκδοχή αλγορίθμου ταξινόμησης με επιλογή και ας εστιάσουμε στην εντολή 3 του εσωτερικού βρόχου και πιο συγκεκριμένα, τόσο στις εντολές καταχώρισης 5-6 μέσα στην εντολή ελέγχου if (εντολή 4), όσο και στην ίδια εντολή if που ενσωματώνει άλλες εντολές.

     procedure select
1.   for i <-- 1 to n-1 do
2.      minj <-- i; minx <-- A[i];
3.      for j <-- i+1 to n do
4.         if A[j]<minx then
5.            minj <-- j;
6.            minx <-- A[j];
7.      A[minj] <-- A[i];
8.      A[i] <-- minx;

Ας υποθέσουμε ότι το κόστος μίας εκτέλεσης του εσωτερικού τμήματος του εσωτερικού βρόχου (δηλαδή μίας εκτέλεσης των εντολών 4-6) είναι φραγμένο από επάνω από μία σταθερά $c_1$. Για μία συγκεκριμένη τιμή της μεταβλητής $i$, ο αριθμός των εκτελέσεων θα είναι $n-i$ και, επομένως, το αθροιστικό κόστος εκτέλεσης των εντολών 4-6 θα είναι $c_1(n-i)$. Αν συνυπολογίσουμε το κόστος αρχικοποίησης της εντολής 3, τότε το μέχρι στιγμής κόστος για τις εντολές 3-6 είναι $c_2+c_1(n-i)$. Στη συνέχεια, εξετάζοντας τον εξωτερικό βρόχο, διακρίνουμε ένα σταθερό κόστος $c_3$ λόγω των δύο εντολών 2, οπότε το κόστος εκτέλεσης του εσωτερικού τμήματος του εξωτερικού βρόχου (δηλαδή των εντολών 2-8) θα είναι: ${\sum }_{i=1}^{n-1}{c}_3+c_2+c_1(n-i)$. Τέλος, στο κόστος αυτό πρέπει να προσθέσουμε ένα σταθερό κόστος $c_4$ για την αρχικοποίηση της εντολής 1. Αν απλοποιήσουμε την προκύπτουσα έκφραση, τότε εύκολα φθάνουμε στην επόμενη έκφραση:

$$T(n)=\frac{c_1}{2}{n}^2+(c_2+c_3-\frac{c_1}{2})n+(c_4-c_3-c_2)$$

(1.2)

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

• •

  το κόστος εκτέλεσης μίας εντολής εντός ενός βρόχου προκύπτει από το γινόμενο του κόστους μίας εκτέλεσης της εντολής επί τον αριθμό των επαναλήψεων,

• •

  το κόστος εκτέλεσης μίας εντολής εντός ενός φωλιασμένου βρόχου προκύπτει από το γινόμενο του κόστους μίας εκτέλεσης της εντολής επί τον αριθμό των επαναλήψεων όλων των βρόχων (επιχειρούμε την ανάλυση από μέσα προς τα έξω).

• •

  σε περίπτωση διαδοχικών εντολών εστιάζουμε στην εντολή με το μεγαλύτερο κόστος,

• •

  το κόστος εκτέλεσης μίας εντολής ελέγχου (if) ισούται με το κόστος του ελέγχου συν το κόστος της διακλάδωσης με το μεγαλύτερο κόστος.

Συνήθως εστιάζουμε στο πιο εσωτερικό σημείο των βρόχων, με προτίμηση στους πολυπλοκότερους (δηλαδή στους φωλιασμένους με περισσότερα επίπεδα). Ωστόσο, χρειάζεται ιδιαίτερη προσοχή στο χειρισμό των ορίων των βρόχων. Το επόμενο παράδειγμα είναι χαρακτηριστικό. Ο μικρός αυτός ψευδοκώδικας υποθέτει ότι υπάρχει ένας πίνακας $A$ με $n$ ακεραίους, για τους οποίους ισχύει $0\le A[i]\le i$, ενώ επίσης δίνεται ότι το άθροισμα αυτών των ακεραίων ισούται με $s$.

1.   k <-- 0;
2.   for i <-- 1 to n do
3.      for j <-- 1 to A[i] do
4.         k <-- k + A[j];

Για κάθε τιμή της μεταβλητής $i$, η εντολή 4 θα εκτελεσθεί $A[i]$ φορές, επομένως συνολικά για όλες τις τιμές της μεταβλητής $i$ (δηλαδή από 1 μέχρι $n$), το πλήθος των επαναλήψεων θα είναι ${\sum }_{i=1}^{n}A[i]=s$. Θα μπορούσε κάποιος να υποστηρίξει ότι η επίδοση του μικρού αυτού ψευδοκώδικα είναι της τάξης του $s$. Για αντιπαράδειγμα, όμως, ας υποθέσουμε ότι $A[i]=1$ αν το $i$ είναι τέλειο τετράγωνο, αλλιώς ισχύει $A[i]=0$. Στην περίπτωση αυτή ισχύει $s=\sqrt{n}$. Όμως κάτι τέτοιο δεν μπορεί να ισχύει, γιατί οπωσδήποτε θα ελεγχθούν όλες οι θέσεις του πίνακα $A$ μεγέθους $n$ (και τουλάχιστον μία φορά η κάθε μία).

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

Η ορθή προσέγγιση, λοιπόν, πρέπει να ακολουθήσει τη μεθοδολογία του παραδείγματος της ταξινόμησης με επιλογή. Αν $c_1$ είναι το κόστος μίας εκτέλεσης του εσωτερικού βρόχου, ενώ $c_2$ είναι το κόστος αρχικοποίησης του βρόχου αυτού, τότε το κόστος των εντολών 3-4 είναι $c_2+c_{1}A[i]$. Με παρόμοιο τρόπο, αν $c_3$ είναι το κόστος μίας εκτέλεσης του εξωτερικού βρόχου, ενώ $c_4$ είναι το κόστος αρχικοποίησης του βρόχου αυτού, τότε προφανώς το κόστος των εντολών 2-4 είναι $c_4+{\sum }_{i=1}^n(c_3+c_2+c_{1}A[i])$. Αν αυτή η έκφραση απλοποιηθεί, τότε προκύπτει $(c_3+c_2)n+c_{1}s+c_4$. Συνεπώς, το κόστος του προηγούμενου ψευδοκώδικα είναι γραμμική συνάρτηση δύο μεταβλητών, του $n$ και του $s$.

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

Μία συμβολοσειρά (string) λέγεται παλίνδρομο (palindrome) αν διαβάζεται το ίδιο είτε από την αρχή είτε από το τέλος (θυμηθείτε το βυζαντινό «νίψον ανομήματα μη μόναν όψιν»). Ο ψευδοκώδικας που ακολουθεί βρίσκει ένα παλίνδρομο σε μία συμβολοσειρά εισόδου που αποθηκεύεται σε ένα πίνακα S μήκους n. Τον αλγόριθμο αυτό θα αναλύσουμε, ώστε να γνωρίζουμε τη συμπεριφορά του σε τρεις περιπτώσεις: την καλύτερη, τη χειρότερη και τη μέση.

     procedure palindrome
1.   left <-- 1; right <-- n; flag <-- false;
2.   while (left<right) and (S[left]=S[right]) do
3.      left <-- left+1; right <-- right-1;
4.   if (left>=right) then flag <-- true;

Για ευκολία της ανάλυσης θα υποθέσουμε ότι η συμβολοσειρά είναι δυαδική. Η κρίσιμη εντολή βαρόμετρο είναι η εντολή 3 μέσα στο βρόχο while. Αν ισχύει S[1]<>S[n], δηλαδή διαφέρει ο πρώτος και ο τελευταίος χαρακτήρας, τότε δεν εκτελείται ο βρόχος και ο αλγόριθμος τερματίζει. Αυτή είναι η καλύτερη περίπτωση και επομένως συμπεραίνουμε ότι στην περίπτωση αυτή η πολυπλοκότητα είναι Θ(1). Η χειρότερη περίπτωση συμβαίνει όταν η συμβολοσειρά είναι ένα παλίνδρομο, οπότε ο βρόχος θα εκτελεσθεί $n/2$ φορές. Στην περίπτωση αυτή η πολυπλοκότητα είναι Θ($n$).

Για να μελετήσουμε τη μέση περίπτωση θα πρέπει να εξετάσουμε όλες τις συμβολοσειρές μήκους $n$. Καθώς υποθέτουμε ότι το αλφάβητό μας έχει μόνο δύο χαρακτήρες, έπεται ότι υπάρχουν $2^n$ διαφορετικές συμβολοσειρές. Κατ’αρχάς υποθέτουμε ότι το $n$ είναι άρτιος αριθμός. Επομένως, $2^n/2$ συμβολοσειρές διαφέρουν στον πρώτο και τελευταίο χαρακτήρα, οπότε δεν θα εκτελεσθεί το σώμα του βρόχου while (εντολή 3). Επίσης, $2^n/2^2$ συμβολοσειρές διαφέρουν στο δεύτερο και προτελευταίο χαρακτήρα, οπότε το σώμα του βρόχου while θα εκτελεσθεί μία φορά. Με το ίδιο σκεπτικό, $2^n/2^{n/2}$ συμβολοσειρές διαφέρουν στους δυο κεντρικούς χαρακτήρες, οπότε το σώμα του βρόχου θα εκτελεσθεί $n/2-1$ φορές. Τελικά, ο αριθμός των παλίνδρομων είναι $2^{n/2}$, οπότε θα γίνουν $n/2$ επαναλήψεις του βρόχου. Συνεπώς, η μέση τιμή των επαναλήψεων δίνεται από τη σχέση:

$$T_{even}(n)=\frac{1}{2^n}\left(\sum _{i=0}^{n/2-1}\frac{2^n}{2^{i+1}}i+2^{n/2}\frac{n}{2}\right)=\sum _{i=1}^{n/2-1}\frac{i}{2^{i+1}}+\frac{n/2}{2^{n/2}}$$

(1.3)

Κατ’ αρχάς θα επιλύσουμε το άθροισμα και θα επανέλθουμε. Πρώτον, λοιπόν, αναπτύσσουμε το άθροισμα και δεύτερον πολλαπλασιάζουμε επί δύο.

	${\displaystyle \sum _{i=0}^{n/2-1}}{\displaystyle \frac{i}{2^{i+1}}}=A$	$=$	${\displaystyle \frac{1}{2^2}}+{\displaystyle \frac{2}{2^3}}+{\displaystyle \frac{3}{2^4}}+\mathrm{\dots }+{\displaystyle \frac{n/2-1}{2^{n/2}}}\Rightarrow$
	$2A$	$=$	${\displaystyle \frac{1}{2^1}}+{\displaystyle \frac{2}{2^2}}+{\displaystyle \frac{3}{2^3}}+\mathrm{\dots }+{\displaystyle \frac{n/2-1}{2^{n/2-1}}}$

Αφαιρώντας κατά μέλη και απλοποιώντας προκύπτει:

$$A=\frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^3}+\mathrm{\dots }+\frac{1}{2^{n/2-1}}-\frac{n/2-1}{2^{n/2}}=\sum _{i=1}^{n/2}\frac{1}{2^i}-\frac{n/2}{2^{n/2}}$$

(1.4)

Τώρα πρέπει να επιλυθεί το τελευταίο άθροισμα. Και πάλι με ανάπτυξη και πολλαπλασιασμό επί δύο και αφαίρεση κατά μέλη προκύπτει:

	${\displaystyle \sum _{i=1}^{n/2}}{\displaystyle \frac{1}{2^i}}=B$	$=$	${\displaystyle \frac{1}{2^1}}+{\displaystyle \frac{1}{2^2}}+{\displaystyle \frac{1}{2^3}}+\mathrm{\dots }+{\displaystyle \frac{1}{2^{n/2}}}\Rightarrow$
	$2B$	$=$	${\displaystyle \frac{1}{2^0}}+{\displaystyle \frac{1}{2^1}}+{\displaystyle \frac{1}{2^2}}+\mathrm{\dots }+{\displaystyle \frac{1}{2^{n/2-1}}}\Rightarrow$
	$B$	$=$	${\displaystyle \frac{1}{2^0}}-{\displaystyle \frac{1}{2^{n/2}}}$

Επομένως, τελικά ισχύει:

$$T_{even}(n)=1-\frac{1}{2^{n/2}}$$

(1.5)

Όταν το $n$ είναι περιττό, πρέπει να λάβουμε υπόψη ότι τώρα υπάρχουν δύο φορές $2^{\frac{n-1}{2}}$ παλίνδρομα με διαφορετικούς χαρακτήρες στην κεντρική θέση και ότι το προηγούμενο άθροισμα έχει πλέον $\frac{n-1}{2}$ όρους. Με κατάλληλη άλγεβρα προκύπτει ότι:

$$T_{odd}(n)=1-\frac{1}{2^{\frac{n-1}{2}}}$$

(1.6)

Επομένως, τελικά προκύπτει ότι η πολυπλοκότητα στη μέση περίπτωση είναι σταθερή Θ(1).

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

Το αντικείμενο της Σχεδίασης και Ανάλυσης Αλγορίθμων (Design and Analysis of Algorithms) είναι εξαιρετικά πλούσιο, όπως μπορεί να φανεί από την βιβλιογραφία, όπου σκοπίμως παρατίθενται μερικά σημαντικά βιβλία που χρονολογούνται από τη δεκαετία του 1970 [2, 152] και τη δεκαετία του 1980 [3, 64, 141, 166, 196]. Για το ίδιο λόγο στη βιβλιογραφία συμπεριλαμβάνονται και μερικά παλαιά άρθρα, που θα αναφερθούν στην ώρα τους. Πιο πρόσφατα είναι τα βιβλία [34, 35, 78, 99]. Ιδιαιτέρως, στο βιβλίο των Dasgupta-Παπαδημητρίου-Vazirani [35] συμπεριλαμβάνεται και κεφάλαιο με τις τελευταίες εξελίξεις του κβαντικού υπολογισμού.

Το τρίτομο μνημειώδες έργο του Knuth πρωτοεκδόθηκε τη δεκαετία του 1970 αλλά επανεκδίδεται μέχρι τις ημέρες μας [88, 89, 92], καθώς είναι κλασικό βιβλίο αναφοράς. Το 1999 το Scientific American, υψηλού επιπέδου περιοδικό ευρείας κυκλοφορίας, κατέταξε το έργο αυτό μεταξύ των 12 καλύτερων επιστημονικών μονογραφιών του 20ου αιώνα μαζί με τα έργα των Dirac για την κβαντομηχανική, του Einstein για τη σχετικότητα, του Mandelbrot για τα fractals, του Pauling για τους χημικούς δεσμούς, των Russell-Whitehead για τις θεμελιώσεις των μαθηματικών, των von Neumann-Morgenstern για τη θεωρία παιγνίων, του Wiener για την κυβερνητική, των Woodward-Hoffmann για τις τροχιακές συμμετρίες, του Feynman για την κβαντο-ηλεκτροδυναμική, του Smith για την αναζήτηση δομής και τη συλλογή των άρθρων του Einstein.

Σημαντικό, επίσης, είναι και το τρίτομο έργο του Mehlhorn [124, 125, 126], ευρέως φάσματος, όπως το τρίτομο βιβλίο του Knuth χωρίς να περιέχονται αλγόριθμοι Αριθμητικής Ανάλυσης (Numerical Analysis), συμπεριλαμβάνοντας όμως αλγορίθμους Γραφικών (Graphics) και Υπολογιστικής Γεωμετρίας (Computational Geometry).

Εκλαϊκευτικά άρθρα έχουν δημοσιευθεί στο Scientific American από τους Lewis-Παπαδημητρίου [101] και τον Knuth [91]. Εισαγωγικά παραδείγματα ανάλυσης αλγορίθμων μεταξύ άλλων αναφέρονται στα άρθρα [47, 56, 184]. Τέλος, η Εξίσωση 1.1 προέρχεται από την προμετωπίδα των βιβλίων του Wirth [199, 200].

Τα μοντέλα μηχανής ακολουθούν την προσέγγιση του βιβλίου του Mehlhorn [126]. Το μοντέλο της Μηχανής Δεικτών προτάθηκε με ισοδύναμους ορισμούς από σειρά ερευνητών αλλά η τελική του μορφή δόθηκε από τον Tarjan [182]. Ο Schönhage έδειξε ότι η Μηχανή Δεικτών μπορεί να προσομοιώσει τη λειτουργία της μηχανής Turing [159] .

Ο «πολλαπλασιασμός αλά ρωσικά» αναφέρεται στη βιβλιογραφία κατά κόρον με τη συγκεκριμένη ονομασία, και επίσης, όπως αναφέρεται, ήταν γνωστός στην αρχαία Αίγυπτο αλλά και στον al Khowarizmi. Στις αριθμητικές πράξεις των αρχαίων Αιγυπτίων αναφέρεται το άρθρο [53]. Το υλικό για το παλίνδρομο προέρχεται από το άρθρο [47]. Η Άσκηση 2 αναφέρεται στο βιβλίο του Bentley [13], οι Ασκήσεις 13-14 βασίζονται στο άρθρο [56], ενώ η Άσκηση 15 αναφέρεται στο βιβλίο του Gries [69].

1. 1.

   Δίνεται ένα σύνολο με $n$ θετικούς πραγματικούς αριθμούς. Θα εκτελέσουμε το εξής πείραμα: Επιλέγουμε από το σύνολο τυχαία 2 αριθμούς και αντικαθιστούμε τον καθένα με το μέσο όρο τους. Η ερώτηση είναι αν αυτό το πείραμα θα τελειώσει ποτέ, δηλαδή το σύνολο θα αποτελείται από $n$ ίσους αριθμούς; Δηλαδή, μπορούμε να σχεδιάσουμε έναν αλγόριθμο με περατότητα ή πρόκειται απλώς για μία υπολογιστική διαδικασία;

2. 2.

   Δίνεται ένα δοχείο με κόκκινα και πράσινα μήλα, καθώς επίσης και ένας σωρός με έξτρα πράσινα μήλα. Θα εκτελέσουμε το εξής πείραμα: Επιλέγουμε 2 μήλα από το δοχείο. Αν είναι ομοιόχρωμα, τότε τα απομακρύνουμε και εισάγουμε στο δοχείο 2 πράσινα μήλα από τα έξτρα. Αν δεν είναι ομοιόχρωμα, τότε απομακρύνουμε το πράσινο, ενώ το κόκκινο επιστρέφεται στο δοχείο. Η ερώτηση είναι αν αυτό το πείραμα θα τελειώσει ποτέ, δηλαδή θα βρεθεί ποτέ το δοχείο με ένα μόνο μήλο; Δηλαδή, μπορούμε να σχεδιάσουμε έναν αλγόριθμο με περατότητα ή πρόκειται απλώς για μία υπολογιστική διαδικασία; Μπορούμε να βρούμε το χρώμα του τελευταίου μήλου με βάση το αρχικό πλήθος των κόκκινων και των πράσινων μήλων;

3. 3.

   Να σχεδιασθεί και να αναλυθεί ένας αλγόριθμος διαίρεσης ακεραίων εφαρμόζοντας την τεχνική του «πολλαπλασιασμού αλά ρωσικά» με την αντίστροφη λογική.

4. 4.

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

5. 5.

   Για το επόμενο τμήμα ψευδοκώδικα να γίνει επακριβής ανάλυση και να υπολογισθεί ο συμβολισμός Ο.

   sum <-- 0;
   for i <-- 1 to n
      for j <-- 1 to i*i
         for k <-- 1 to j
            sum <-- sum+1;
   

6. 6.

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

   sum <-- 0;
   for i <-- 1 to n
      for j <-- 1 to i*i
         if (j mod i =0) then
            for k <-- 1 to j
               sum <-- sum+1;
   

7. 7.

   Δίνεται ένας πίνακας A[0..n-1] με $n$ διακριτούς ακεραίους. Ο επόμενος ψευδοκώδικας υπολογίζει τον αριθμό των αντιστροφών (inversions), δηλαδή των περιπτώσεων όπου A[i]<A[j] αλλά i>j. Να υπολογισθεί ο συμβολισμός Ο. Μπορεί να υπάρξει βελτίωση στον ψευδοκώδικα; Να υπολογισθεί εκ νέου ο συμβολισμός Ο.

   procedure InvCount;
   counter <-- 0;
   for i <-- 1 to n do
      for j <-- 1 to n do
         if (i<j) and (A[i]>A[j]) then counter <-- counter+1;
   

8. 8.

   Η ταξινόμηση της φυσαλίδας (bubblesort) ή ταξινόμηση με ανταλλαγές (exchange sort) είναι γνωστή από το αντικείμενο των Δομών Δεδομένων. Η διαδικασία bubblesort ταξινομεί επιτοπίως (in-place) τον πίνακα Α:[1..n]. Ποια εντολή είναι το βαρόμετρο; Να γίνει κοστολόγηση του αλγορίθμου και να βρεθεί η πολυπλοκότητα στην καλύτερη, μέση και χειρότερη περίπτωση.

   procedure bubblesort
   for i <-- 0 to n-2 do
      for j <-- 0 to n-2 do
         if A[j+1]<A[j] then
            temp <-- A[j];
            A[j] <-- A[j+1];
            A[j+1] <-- temp;
   

9. 9.

   Δίνεται η επόμενη παραλλαγή της ταξινόμησης της φυσαλίδας. Η παραλλαγή αυτή να κοστολογηθεί ομοίως και να συγκριθεί με την προηγούμενη μέθοδο.

   procedure bubblesort
   for i <-- 0 to n-2 do
      for j <-- 0 to n-2-i do
         if A[j+1]<A[j] then
            temp <-- A[j];
            A[j] <-- A[j+1];
            A[j+1] <-- temp;
   

10. 10.

    Δίνεται πίνακας A[0..n-1,0..n-1] και ζητείται να βρεθεί η πρώτη θέση ενός στοιχείου x (αν αυτό υπάρχει), όπου με την έκφραση «πρώτη» εννοείται ότι δεν υπάρχει άλλο x σε προηγούμενη γραμμή ή προηγούμενη στήλη. Να σχεδιασθεί αλγόριθμος και να αναλυθεί η καλύτερη, η μέση και η χειρότερη περίπτωση.

11. 11.

    Ο αλγόριθμος findmax δέχεται τον πίνακα Α:[1..n] και εξάγει το ζεύγος max,i, όπου max είναι το μέγιστο στοιχείο του πίνακα, ενώ i είναι η θέση όπου αυτό εμφανίζεται (όπου $1\le i\le n$). Ο αλγόριθμος να κοστολογηθεί και να βρεθεί η πολυπλοκότητα σε κάθε περίπτωση.

    function findmax(A,n)
    i <-- 1; j <-- 2; m <-- A[1];
    while j <= n do
       if A[j]>max then
          max <-- A[j];
          i <-- j;
       j <-- j+1;
    return(m,i);
    

12. 12.

    Το κόσκινο του Ερατοσθένη (Eratosthenes sieve) είναι μία μέθοδος για την εύρεση των πρώτων αριθμών (δηλαδή των αριθμών που διαιρούνται μόνο από το 1 και τον εαυτό τους) που είναι μικρότεροι του $n$. Ο αλγόριθμος θεωρεί έναν πίνακα με τους ακεραίους από το 2 μέχρι το $n$, βρίσκει το μικρότερο ακέραιο $i$, τον τυπώνει και διαγράφει από τον πίνακα τους ακεραίους $i,2i,3i,\mathrm{\dots }$. Η διαδικασία σταματά, όταν $i>\sqrt{n}$. Ένα παράδειγμα εκτέλεσης του αλγορίθμου για $n=80$ παρουσιάζεται στο Σχήμα 1.3. Να σχεδιασθεί και να αναλυθεί ο αλγόριθμος.

    

13. 13.

    Δίνονται δύο ακέραιοι $y>x>0$ και ζητείται να δοθούν σε φθίνουσα τάξη όλα τα πολλαπλάσια του $x$, που είναι μικρότερα του $y$. Για παράδειγμα, αν $x=100$ και $y=550$, τότε η έξοδος είναι: 500, 400, 300, 200, 100. Να σχεδιασθεί και να αναλυθεί αλγόριθμος επίλυσης του προβλήματος.

14. 14.

    Το έργο $n$ υπαλλήλων είναι να αναβοσβήνουν $m$ λάμπες που βρίσκονται σε έναν ευθύγραμμο δρόμο. Ο πρώτος υπάλληλος ανάβει όλες τις λάμπες. Ο δεύτερος υπάλληλος σβήνει τη δεύτερη, τέταρτη, έκτη κλπ. Ο τρίτος επεμβαίνει στην τρίτη, έκτη, ένατη κλπ και την ανάβει (σβήνει) αν είναι κλειστή (ανοικτή). Ο τέταρτος επεμβαίνει στην τέταρτη, όγδοη, δωδέκατη και αναβοσβήνει αντίστοιχα. Το ζητούμενο είναι να διαπιστωθεί ποίες λάμπες είναι ανοικτές, όταν περάσει ο τελευταίος υπάλληλος. Για την επίλυση του προβλήματος να σχεδιασθεί και να αναλυθεί αλγόριθμος.

15. 15.

    Λέγεται ότι ένας δισδιάστατος πίνακας A[0..n-1,0..n-1] έχει ένα σημείο σέλλας (saddle point), αν υπάρχει ένα στοιχείο A[i,j] που είναι το μικρότερο στοιχείο της γραμμής i και το μεγαλύτερο στοιχείο της στήλης j. Να σχεδιασθεί και να αναλυθεί αλγόριθμος εντοπισμού του σημείου αυτού (αν υπάρχει).

    17	24	1	8	15
    23	5	7	14	16
    4	6	13	20	22
    10	12	19	21	3
    11	18	25	2	9

16. 16.

    Μαγικό τετράγωνο (magic square) λέγεται ένας πίνακας $n\times n$ που περιέχει τους ακέραιους από 1 ως $n^2$ σε τέτοιες θέσεις, ώστε το άθροισμα των τιμών κάθε γραμμής, κάθε στήλης και κάθε κύριας διαγωνίου είναι το ίδιο. Αν το $n$ είναι περιττός αριθμός, τότε η τοποθέτηση των στοιχείων στο τετράγωνο γίνεται ως εξής: Αρχικά τοποθετείται το 1 στην κορυφή της μεσαίας στήλης. Οι ακέραιοι $2,3,\mathrm{\dots }$ τοποθετούνται σε θέσεις διαγωνίως επάνω και δεξιά. Αν ξεπερασθεί η πρώτη γραμμή, τότε η διαδικασία συνεχίζει στην τελευταία γραμμή, ενώ αν ξεπερασθεί η τελευταία στήλη, τότε η διαδικασία συνεχίζει στην πρώτη στήλη. Αν η επισκεπτόμενη θέση είναι κατειλημμένη, τότε η διαδικασία συνεχίζει μία θέση προς τα κάτω στην ίδια στήλη. Στο Σχήμα 1.4 παρουσιάζεται ένα μαγικό τετράγωνο $5\times 5$, όπου το άθροισμα των στοιχείων κάθε γραμμής, στήλης ή κύριας διαγωνίου είναι 65. Να σχεδιασθεί ένας αλγόριθμος που να διαπιστώνει αν ένας δισδιάστατος πίνακας είναι πράγματι μαγικό τετράγωνο. Επίσης, να σχεδιασθεί ένας αλγόριθμος κατασκευής ενός μαγικού τετράγωνου περιττής τάξης. Σε κάθε περίπτωση να αναλυθούν οι αντίστοιχοι αλγόριθμοι.