Βασικές Πράξεις

Βασική πράξη θεωρούμε ότι είναι οποιαδήποτε πράξη της οποίας ο χρόνος εκτέλεσης είναι φραγμένος από κάποια σταθερά, δηλαδή, T(n)<=c για κάποια σταθερά c.

Στις βασικές πράξεις περιλαμβάνονται:

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

Συνεπώς, ο χρόνος εκτέλεσης μιας βασικής πράξης μπορεί να προσδιοριστεί ανεξάρτητα από το στιγμιότυπο (π.χ ο χρόνος εκτέλεσης του 10+3 είναι ο ίδιος με του 10000+3).

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

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

Απλοί Βρόχοι

Ας υποθέσουμε ότι ένα πρόβλημα λύνεται από ένα βρόχο ο οποίος επαναλαμβάνεται n φορές και μέσα σ' αυτό το βρόχο εκτελεί βασικές πράξεις.

Όπου s η βασική πράξη. Η s εκτελείται n φορές. Αν Τ₂ ο χρόνος που χρειάζεται για να εκτελεστεί (το 2 υποδηλώνει τον αριθμό της γραμμής που βρίσκεται η εντολή στον παραπάνω αλγόριθμο), τότε εκτελείται συνολικά nT₂ φορές.

Ο συνολικός χρόνος, λοιπόν, είναι:

Επειδή, όπως αναφέραμε και παραπάνω, τα Τ₁ και Τ₂ είναι βασικές πράξεις, έχουν σταθερή πολυπλοκότητα, δηλαδή Θ(1). Οπότε αυτό που καθορίζει το χρόνο εκτέλεσης είναι το n.

Συνεπώς, ο αλγόριθμος είναι γραμμικής τάξης και η χρονική πολυπλοκότητά του είναι O(n).

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

Εμφολιασμένοι Βρόχοι

Σ΄ αυτή την περίπτωση έχουμε βρόχο μέσα σε βρόχο. Είναι συνηθισμένη περίπτωση στην ταξινόμηση πινάκων. Τα παραδείγματα είναι όμοια με εκείνο στον απλό βρόχο.

Ανεξάρτητοι Βρόχοι

Αυτό σημαίνει ότι το i (εσωτερικός βρόχος) δεν εξαρτάται από την τιμή του j (εξωτερικός βρόχος) αλλά μόνο από το πλήθος των επαναλήψεων (n).

Όπως είδαμε, ο εσωτερικός βρόχος χρειάζεται χρόνο:

Ο εξωτερικός βρόχος χρειάζεται χρόνο Τ₁ για την ανάθεση τιμής και τη σύγκριση, όπως έχουμε πει, και οι λειτουργίες αυτές γίνονται n φορές, οπότε ο χρόνος που χρειάζεται συνολικά είναι nT₁. Για κάθε μία επανάληψη του εξωτερικού βρόχου, οι εντολές τους χρειάζονται χρόνο T_2,3. Οπότε για τις n συνολικά επαναλήψεις, οι εντολές του χρειάζονται nT_2,3 χρόνο.

Ο συνολικός χρόνος που χρειάζεται ο αλγόριθμος είναι:

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

Εξαρτημένοι Βρόχοι - Γραμμική Εξάρτηση

Αυτό σημαίνει ότι το i (εσωτερικός βρόχος) εξαρτάται από την τιμή του j (εξωτερικός βρόχος). Στο παράδειγμα μας, το i μεταβάλλεται μεταξύ 1 και της τιμής του j.

Σ' αυτό το παράδειγμα, το πόσες φορές επαναλαμβάνεται ο εσωτερικός βρόχος εξαρτάται από την τιμή του j στον εξωτερικό βρόχο. Έτσι, όταν το j = 1, ο εσωτερικός βρόχος επαναλαμβάνεται 1 φορά και η εντολή s επίσης μία φορά, όταν j = 2, επαναλαμβάνεται 2 φορές και η s 2 φορές κ.ο.κ. μέχρι να επαναληφθεί n φορές όταν j = n.

Οπότε, ο χρόνος που χρειάζεται η εντολή στη γραμμή 3 για να εκτελεστεί είναι:

Για	Επαναλήψεις εσωτερικού βρόχου	Χρόνος εκτέλεσης εντολής s
j=1	1	T3
j=2	2	2T3
j=3	3	3T3
...	...	...
j=n	n	nT3

Ο συνολικό χρόνος υπολογίζεται ως:

Όμοια, ο χρόνος που χρειάζεται στη γραμμή 2 για ανάθεση τιμής στο i και σύγκρισή του με το j είναι:

Για	Χρόνος εκτέλεσης εντολής
j=1	T2
j=2	2T2
j=3	3T2
...	...
j=n	nT2

Άρα ο συνολικός χρόνος για να εκτελεστούν οι γραμμές 2 και 3, είναι το άθροισμα των δύο παραπάνω αποτελεσμάτων.

Ο χρόνος εκτέλεσης της γραμμής 1, όπως είδαμε και στα προηγούμενα παραδείγματα είναι T₁ και η επανάληψη του βρόχου n φορές, άρα ο συνολικός χρόνος της γραμμής είναι nT₁. Ο συνολικός χρόνος τώρα του αλγόριθμου είναι:

ΠΡΟΣΟΧΗ: Δεν έχουμε nT2,3 γιατί ο χρόνος T2,3 έχει ήδη υπολογιστεί για n επαναλήψεις του εξωτερικού βρόχου. Οπότε είναι λάθος να τον υπολογίσουμε n φορές ξανά!

Έχουμε, λοιπόν:

Στον παραπάνω τύπο, ο όρος με τη μεγαλύτερη βαρύτητα είναι ο n². Οπότε χρονική πολυπλοκότητα του αλγόριθμου είναι Ο(n²), δηλαδή, είναι τετραγωνικής πολυπλοκότητας όπως και η προηγούμενη περίπτωση.

Εξαρτημένοι Βρόχοι - Μη Γραμμική Εξάρτηση

Αναδρομή

Τεχνικές "Διαίρει και Βασίλευε"

Οι αναδρομικές σχέσεις των τεχνικών αυτών έχουν τον γενικό τύπο:

Δηλαδή, υπάρχει ένα σταθερό κομμάτι συνεισφοράς (κόστος), το cn σε κάθε βήμα στο οποίο ελαττώνεται ο αλγόριθμος (n/2). Αυτό φαίνεται παραστατικά στο παρακάτω σχήμα.

Σε κάθε επανάληψη του αλγόριθμου το πρόβλημα διαιρείται σε 2 υποπροβλήματα που χρειάζονται τον μισό χρόνο εκτέλεσης. Το δένδρο αυτό προχωράει σε βάθος μέχρις ότου n/2ⁱ=1.

Άρα, το δέντρο αυτό έχει logn + 1 επίπεδα (προσθέτουμε και τη ρίζα – επίπεδο 0). Συνολικά, έχουμε nlogn+1 επαναλήψεις του cn, οπότε, ο χρόνος είναι:

Ο όρος που υπερισχύει στον παραπάνω τύπο είναι ο cnlogn, έτσι, η πολυπλοκότητά της αναδρομικής αυτής σχέσης είναι O(nlogn) (διαβάζεται “νι λογκ νι”).

Κάτω φράγμα στον αριθμό συγκρίσεων