Υπολογισμός χρόνου εκτέλεσης (υπολογισμός αριθμού πράξεων των εντολών)

[SPY]

Το βιβλίο πάντως στον αλγόριθμο παράδειγμα στο κεφάλαιο 5.1 έχει λάθος σύμφωνα με αυτά που μας λέει για τις πράξεις... η αύξηση του i πρέπει να είναι 2 πράξεις... Δηλαδή και στον αλγόριθμο ταξινόμησης 1 πράξη είναι η αύξηση του μετρητή σε κάθε επανάληψη;;;;

Ίσως να είναι λάθος. Το θέμα όμως είναι ότι διδάσκουμε μαθητές-υποψηφίους. Εφόσον λοιπόν εξετάζονται με βάση το σχολικό βιβλίο, η αύξηση του μετρητή μιας ΓΙΑ είναι μια πράξη. Αν ερωτηθούν στις εξετάσεις (ελπίζω να μη συμβεί) αυτό δεν πρέπει να γράψουν;

[meteo_xampos]

Ναι συμφωνώ, εφόσον το λέει το βιβλίο έτσι πρέπει να το κάνουμε... Όμως για να καταλάβουν οι μαθητές μου πόσες πράξεις κάνει η Για, την μετατρέπω σε Οσο, οπότε στην μετατροπή φανερώνεται η πράξη i<-i+1... Προτιμώ να κατανοούν τι γίνεται τα κοπέλια παρά να παπαγαλίζουν... Τι λες όμως τότε, ότι το βιβλίο λέει μπούρδες, και ότι το i<-i+1 είναι μια πράξη;

[annastasios]

Επειδή η αύξηση i
ισοδυναμεί με
i<-- 1 +1
πιστεύω αριθμός πράξεων: 2

επομένως θέλει διόρθωση το παράδειγμα 5,1,3

Παρακαλώ πείτε κι υπόλοιποι τη γνώμη σας

[annastasios]

Επειδή η αύξηση i
ισοδυναμεί με
i<-- 1 +1
πιστεύω αριθμός πράξεων: 2

επομένως θέλει διόρθωση το παράδειγμα 5,1,3

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

Επομένως το παράδειγμα είναι σωστό

[petrosp13]

Θα το διδάξουμε όπως το λέει το βιβλίο για φέτος. Έστω κι αν θεωρούμε ότι είναι λάθος

[SPY]

Ναι συμφωνώ, εφόσον το λέει το βιβλίο έτσι πρέπει να το κάνουμε... Όμως για να καταλάβουν οι μαθητές μου πόσες πράξεις κάνει η Για, την μετατρέπω σε Οσο, οπότε στην μετατροπή φανερώνεται η πράξη i<-i+1... Προτιμώ να κατανοούν τι γίνεται τα κοπέλια παρά να παπαγαλίζουν... Τι λες όμως τότε, ότι το βιβλίο λέει μπούρδες, και ότι το i<-i+1 είναι μια πράξη;

Αυτό που σίγουρα κατανοούν τα κοπέλια (και οι κοπελούδες υποθέτω) είναι ότι τα σχολικά βιβλία γράφονται στο πόδι από ανεύθυνους "επιστήμονες" και κανείς δεν ενδιαφέρεται να τα βελτιώσει μετά από 17 χρόνια. "Αυτή είναι η Ελλάδα", που είχε πει και ο μέγας καταστροφέας. Τι να προσθέσεις εσύ βρε συνάδελφε;
Τώρα επί της ουσίας νομίζω ότι καλό είναι να μην μετατρέπεις τη ΓΙΑ στην ισοδύναμη ΟΣΟ για να μετρηθούν οι πράξεις. Άλλωστε σε επίπεδο μεταφραστή δεν είναι σίγουρο ότι η ΓΙΑ και η ισοδύναμη ΟΣΟ παράγουν τον ίδιο κώδικα σε γλώσσα μηχανής. Νομίζω ότι κάπου αναφέρθηκε αυτό από κάποιο συνάδελφο για κάποια Pascal. Επομένως μπορεί να δοθεί μια "ικανοποιητική" απάντηση σε απορία μαθητή.

[meteo_xampos]

Και οι μετατροπές από Για σε Όσο γιατί γίνονται; Τεσπα... Θα ακολουθήσουμε το σχολικό και έχει ο θεός... Ελπίζω να μη βάλουν κανένα τέτοιο θέμα... Καλή μας συνέχεια!!!

[semaphore]

Το να ακολουθήσουμε το βιβλίο ως έχει είναι διφορούμενο ως απάντηση. Και αυτό γιατί σελίδα 98 αναφέρει "Για παράδειγμα, μία βασική πράξη μπορεί να είναι:
    ανάθεση τιμής,
    σύγκριση μεταξύ δύο μεταβλητών, ή
    οποιαδήποτε αριθμητική πράξη μεταξύ δύο μεταβλητών."

Έπειτα, στο παράδειγμα (σελ 100)  αυτο-ακυρώνεται το προηγούμενο, με την εν λόγω δικαιολόγηση της απάντησης (αύξηση i --> 5).

Δε συμφωνώ με το επιχείρημα "ας το ακολουθήσουμε και ας ελπίσουμε να μην πέσει κάτι τέτοιο στα φετεινά θέματα".

Γιατί:

1. ΜΠΟΡΕΙ και να πέσει τέτοιο θέμα και μετά θα τρέχουμε να βρούμε ποια είναι η σωστή απάντηση (όπου ΟΛΕΣ θα είναι οι σωστές απαντήσεις).
2. Σε τυχόν απορίες από "καλούς και ψαγμένους" μαθητές , θα κολλήσουμε και εμείς οι ίδιοι , γιατί δε θα ξέρουμε τί να απαντήσουμε.

Προτείνω να απαντήσει σε αυτό το θέμα κάποιος που είναι αρμόδιος για αποφυγή των παραπάνω όσο είναι ακόμα καιρός.

[Diotima]

Αυτό που σίγουρα κατανοούν τα κοπέλια (και οι κοπελούδες υποθέτω) είναι ότι τα σχολικά βιβλία γράφονται στο πόδι από ανεύθυνους "επιστήμονες" και κανείς δεν ενδιαφέρεται να τα βελτιώσει μετά από 17 χρόνια. "Αυτή είναι η Ελλάδα", που είχε πει και ο μέγας καταστροφέας. Τι να προσθέσεις εσύ βρε συνάδελφε;
Τώρα επί της ουσίας νομίζω ότι καλό είναι να μην μετατρέπεις τη ΓΙΑ στην ισοδύναμη ΟΣΟ για να μετρηθούν οι πράξεις. Άλλωστε σε επίπεδο μεταφραστή δεν είναι σίγουρο ότι η ΓΙΑ και η ισοδύναμη ΟΣΟ παράγουν τον ίδιο κώδικα σε γλώσσα μηχανής. Νομίζω ότι κάπου αναφέρθηκε αυτό από κάποιο συνάδελφο για κάποια Pascal. Επομένως μπορεί να δοθεί μια "ικανοποιητική" απάντηση σε απορία μαθητή.

Συμφωνώ μαζί σου SPY, είχαμε συζητήσει μαζί το θέμα και παλιότερα.
Η συζήτηση που ήδη έχει γίνει εδώ και που δίνεται μια απάντηση μέσω της Pascal βρίσκεται εδώ
https://alkisg.mysch.gr/steki/index.php?topic=6526.0
και είναι πολύ κατατοπιστική.

Επίσης θέλω να προτείνω και το πολύ ωραίο άρθρο του Διονύση Ζήνδρου,
"Μια Εύπεπτη Εισαγωγή στην Ανάλυση Πολυπλοκότητας Αλγορίθμων"
http://discrete.gr/complexity/?el

Θεωρώ ότι είναι πολύ κατατοπιστικό για το θέμα της συζήτησης αλλά και για όλο το 5ο κεφάλαιο.
Στην παράγραφο "Μετρώντας εντολές" ο συγγραφέας δίνει ένα παράδειγμα εύρεσης μέγιστου σε έναν μονοδιάστατο πίνακα με τον κώδικα σε Javascript.
Όπως γράφει, υποθέτει ότι ο επεξεργαστής μπορεί να εκτελέσει την αύξηση μια τιμής ως μία βασική εντολή (πράξη), οπότε η αύξηση του i στο for θεωρείται ως μία βασική εντολή.

Στην παράγραφο "Ασυμπτωτική συμπεριφορά" του ίδιου άρθρου αναφέρεται και το εξής:

"Η πράξη της "εύρεσης στοιχείου πίνακα" μπορεί να μεταγλωττίζεται σε διαφορετικές εντολές σε διαφορετικές γλώσσες προγραμματισμού. Για παράδειγμα, στη C, όταν κάνουμε A[ i ] η γλώσσα δεν ελέγχει ότι το i είναι εντός των δηλωμένων ορίων του πίνακα, ενώ στην Pascal αυτός ο έλεγχος γίνεται. Συνεπώς, ο ακόλουθος κώδικας σε Pascal:
M := A[ i ]

είναι ισοδύναμος με τον ακόλουθο κώδικα σε C:
if ( i >= 0 && i < n ) {
M = A[ i ];
}
Οπότε είναι λογικό να περιμένουμε ότι οι διαφορετικές γλώσσες προγραμματισμού θα οδηγήσουν σε διαφορετικούς συντελεστές όταν μετράμε τις εντολές τους. Στο παράδειγμά μας όπου χρησιμοποιούμε έναν χαζό μεταγλωττιστή για την Pascal ο οποίος δεν ξέρει τίποτα για πιθανές βελτιστοποιήσεις, η Pascal χρειάζεται 3 εντολές για κάθε πρόσβαση σε στοιχείο πίνακα αντί για τη 1 εντολή που χρειάζεται η C. Το ότι πετάμε αυτό το συντελεστή είναι συμβατό με την ιδέα ότι αγνοούμε τις διαφορές ανάμεσα σε συγκεκριμένες γλώσσες προγραμματισμού και μεταγλωττιστές και αναλύουμε μόνο την ιδέα του ίδιου του αλγορίθμου."

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

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

[ntzios kostas]

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

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

Συμφωνώ απόλυτα.

Παρ' όλα αυτά θα ήθελα να πω και την δικιά μου άποψη σε αυτό που γράφει το σχολικό περί αριθμού βημάτων.

Σύμφωνα με το σχολικό η εντολή χ<-χ+1 θεωρείται μία πράξη ενώ η χ<-α+1 θεωρούνται δύο. Πριν το καταδικάσουμε δείτε τι γίνεται στην X86 Assembly.
x<-x+1 { ADD x,1 ή αλλιώς inc x} που σημαίνει αύξησε το x κατά 1 (μία πράξη)
x<-x*2 {mult x,2} διπλασίασε το x (μία πράξη)
x<-x-1 {dec x} μείωσε το x κατά 1 (μία πράξη)
Όλες οι παραπάνω θεωρούνται μία πράξη- η πράξη της αύξησης, του διπλασιασμού ή της μείωσης. Μάλιστα η πράξη inc x θεωρείται και πιο γρήγορη από το ADD x, 1
Αντίθετα
x<- a+1 {Add a,1,x} που σημαίνει πρόσθεσε το a με το 1 (μία πράξη) και καταχώρισε το αποτέλεσμα στο x (δεύτερη πράξη).
z<-a*b κάνε την πράξη και καταχώρησε το αποτέλεσμα στο z. (Η  bold πρόταση είναι που λείπει στις αυξήσεις μεταβλητών και θεωρούνται  μία πράξη λιγότερη.)

Προσωπικά λοιπόν στους μαθητές θα πω για να είμαι και σύμφωνος με το σχολικό ότι οι αυξήσεις- μειώσεις μίας μεταβλητής κατά μία ποσότητα (απλά πράγματα όχι παραδείγματα της μορφής x<-x^2+1/2)να την θεωρούν μία πράξη ενώ πράξεις τις μορφής z<-a+b δύο.

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

[Γιάννης Αναγνωστάκης]

Συμφωνώ απόλυτα.

Παρ' όλα αυτά θα ήθελα να πω και την δικιά μου άποψη σε αυτό που γράφει το σχολικό περί αριθμού βημάτων.

Σύμφωνα με το σχολικό η εντολή χ<-χ+1 θεωρείται μία πράξη ενώ η χ<-α+1 θεωρούνται δύο. Πριν το καταδικάσουμε δείτε τι γίνεται στην X86 Assembly.
x<-x+1 { ADD x,1 ή αλλιώς inc x} που σημαίνει αύξησε το x κατά 1 (μία πράξη)
x<-x*2 {mult x,2} διπλασίασε το x (μία πράξη)
x<-x-1 {dec x} μείωσε το x κατά 1 (μία πράξη)
Όλες οι παραπάνω θεωρούνται μία πράξη- η πράξη της αύξησης, του διπλασιασμού ή της μείωσης. Μάλιστα η πράξη inc x θεωρείται και πιο γρήγορη από το ADD x, 1
Αντίθετα
x<- a+1 {Add a,1,x} που σημαίνει πρόσθεσε το a με το 1 (μία πράξη) και καταχώρισε το αποτέλεσμα στο x (δεύτερη πράξη).
z<-a*b κάνε την πράξη και καταχώρησε το αποτέλεσμα στο z. (Η  bold πρόταση είναι που λείπει στις αυξήσεις μεταβλητών και θεωρούνται  μία πράξη λιγότερη.)

Προσωπικά λοιπόν στους μαθητές θα πω για να είμαι και σύμφωνος με το σχολικό ότι οι αυξήσεις- μειώσεις μίας μεταβλητής κατά μία ποσότητα (απλά πράγματα όχι παραδείγματα της μορφής x<-x^2+1/2)να την θεωρούν μία πράξη ενώ πράξεις τις μορφής z<-a+b δύο.

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

+++++

[meteo_xampos]

WHo cares about assemply?  Δηλαδή αν δούμε εντολή x<-x+1 σε μια άσκηση με πράξεις, θα πούμε ότι γίνεται 1 πράξη;;;; 

[gthal]

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

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

Όμως αν φτάσουμε σε επίπεδο Assembly θα πρέπει να αμφισβητήσουμε έναν άλλο ισχυρισμό του βιβλίου, το ότι κάθε αριθμητική πράξη είναι ακριβώς μία βασική πράξη (και όχι μόνο αυτόν).
Δεν μπορεί δηλαδή το χ<-χ+1 να το δούμε από τη σκοπιά της assembly ενώ την έκφραση α^β (που σε assembly δεν θα ήταν μία πράξη) να το δούμε αλλιώς. Ή παντού ή πουθενά.
Και το βιβλίο έχει διαλέξει το πουθενά, αφού όλα αυτά που ορίζει ως "βασικές πράξεις" δεν απαιτούν σε καμία περίπτωση το ίδιο πλήθος κύκλων μηχανής.

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

[ntzios kostas]

Γιώργο προσπαθώ να δικαιολογήσω το σχολικό βιβλίο και να δώσω μία βάση σε αυτά που λέει. Για εμένα σύμφωνα και με το σχολικό το χ<-χ+1 είναι μία πράξη. Τώρα αν έρθει κάποια διαφορετική διευκρίνιση θα το δεχτώ και ως δύο.

[Diotima]

Κάθε φορά που διαβάζω το κεφάλαιο 5 αισθάνομαι σαν τον αρχαιολόγο που προσπαθεί να αποκρυπτογραφήσει την Γραμμική Α και να κατανοήσει τι είχε στο μυαλό του σε κάθε σημείο του κειμένου αυτός που το έγραψε.

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

1. Νομίζω ότι κάνουμε λάθος να θεωρούμε ότι το βιβλίο δίνει γενικά και συγκεκριμένα τον ορισμό των "βασικών πράξεων" ενός αλγορίθμου. Και το εξηγώ:

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

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

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

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

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

Αλγόριθμος                 Βασική πράξη
ΤΑΞΙΝΟΜΗΣΗ               σύγκριση
ΠΟΛΛΑΠΛΑΣΙΑΣΜΟΣ     αριθμητικές πράξεις
ΑΝΑΖΗΤΗΣΗ                 σύγκριση

Βέβαια σε έναν αλγόριθμο ταξινόμησης ή αναζήτησης δε γίνονται μόνο συγκρίσεις, αλλά θεωρούμε ως βασικές πράξεις και μετράμε μόνο τις συγκρίσεις κλειδιών, ενώ στον πολλαπλασιασμό μετράμε το πλήθος των αριθμητικών πράξεων που γίνονται. Ορίζουμε λοιπόν ποια θα είναι η βασική πράξη αναλόγως το πρόβλημα και τον αλγόριθμο που θα μελετήσουμε. (Και αυτό μπορεί να απαντήσει και στην απορία ενός μαθητή, γιατί σε αυτούς τους αλγορίθμους μετράμε μόνο αυτές ως βασικές πράξεις και όχι όλες όπως στο παράδειγμα της 5.1.3.)
Στην παράγραφο 5.3.1.Ταξινόμηση ευθείας ανταλλαγής γράφει:
Το πιο βασικό κριτήριο της επίδοσης μίας μεθόδου ταξινόμησης είναι ο αριθμός C, που μετρά τις απαιτούμενες συγκρίσεις κλειδιών (key comparisons), που εκτελούνται μέχρι να τελειώσει η ταξινόμηση. Ένα άλλο κριτήριο είναι ο αριθμός Μ που μετρά τις μετακινήσεις (moves) των στοιχείων.
Θα μπορούσαμε λοιπόν με βάση το βιβλίο να ορίσουμε ως βασική πράξη για την ταξινόμηση τη μετακίνηση ενός στοιχείου.

Το συμπέρασμα μου λοιπόν από όλα αυτά είναι:

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

Και έρχομαι στην επίμαχη παράγραφο 5.1.3.Χρόνος εκτέλεσης προγράμματος ενός αλγορίθμου. Γράφει:
Θα υπολογισθεί η επίδοσή του με βάση τον αριθμό των πράξεων που θα εκτελεσθούν.

Εδώ αναγκάστηκε ο συγγραφέας να μετρήσει όλες τις πράξεις για να δώσει το παράδειγμα (τις οποίες δεν ονομάζει βασικές, ούτε στον πίνακα που ακολουθεί, τις λέει απλώς πράξεις, γιατί άραγε;).
Ξέχασε όμως να ορίσει, πριν μετρήσει, ποιες θα είναι αυτές οι πράξεις που θα αυξάνουν κατά ένα το πλήθος, ίσως αποφάσισε να χρησιμοποιήσει αυτές που αναφέρονται στην παράγραφο 5.1.1., αλλά όταν έφτασε στην αύξηση του i αποφάσισε να τη θεωρήσει ως μία πράξη. Εδώ πιστεύω ότι όντως σκέφτηκε κάποια assembly, εδώ συμφωνώ με τον Κώστα και την πολύ ωραία εξήγηση που έδωσε μέσω της Χ86 Assembly.

ΥΓ: Αν υπάρχει περίπτωση να μπει τέτοιο θέμα θα πρέπει να ορίζει τις βασικές πράξεις με τις οποίες θα γίνει η μέτρηση, διαφορετικά εγώ το θεωρώ ασαφές και ελλιπές. Ήδη έχω μαθητή που ο καθηγητής στο σχολείο μετατρέπει τη Για σε Όσο και μετράει το i <-- i+1 ως δύο πράξεις. Άλλοι θα το μετράνε ως μία πράξη.
Καταλαβαίνετε τι πρόκειται να γίνει....