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

[alkisg]

Νομίζω ότι η διαφωνία είναι στο "ποιο είναι το ερώτημα", όχι "ποια είναι η απάντηση"...
Να αλλάξω ελαφρώς την άσκηση για να γίνει πιο σαφής η διαφωνία;

Έχουμε έναν αλγόριθμο που διαβάζει έναν δισδιάστατο, αλλά όχι τετραγωνικό, πίνακα k*m.

Πόσα στοιχεία διαβάζονται από το πληκτρολόγιο; k*m
Ποιο είναι το μέγεθος της εισόδου; k*m
Πόσες "βασικές πράξεις" ή πόσο χρόνο θα κάνει ο αλγόριθμος; σταθερά*k*m

Ποια είναι η πολυπλοκότητα του αλγορίθμου;
Ωπ, εδώ είμαστε. Πολυπλοκότητα ως προς τι;

1) Η απλή και διαισθητική απάντηση είναι ότι η πολυπλοκότητα είναι O(k*m), επειδή με τα ίδια νούμερα μετρήσαμε και τις πράξεις και το χρόνο εκτέλεσης.
Άρα μετρώντας την πολυπλοκότητα σε σχέση με τις διαστάσεις k, m του πίνακα, είναι O(k*m).
Αυτό νομίζω είναι και το πνεύμα της άσκησης του τετραδίου μαθητή, και γι' αυτό στον τετραγωνικό πίνακα που χρησιμοποιεί, λέει ότι η πολυπλοκότητα είναι O(n*n) = O(n²).

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

Το πρόβλημα λοιπόν είναι αν ρωτάμε το (1) (το οποίο νομίζω ότι λέει ο Λάμπρος), ή το (2) (το οποίο νομίζω ότι λέει ο Γιώργος).

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

[gpapargi]

Λάμπρο αν ισχύει ότι f(n)=2n²+4n+4 δεν μπορεί ταυτόχρονα να ισχύει και f(n²)=2n²+4n+4. Αυτό που θα ισχύει είναι f(n²)=2n⁴+4n²+4 (σύμφωνα με τη σύνθεση συναρτήσεων)

Άλκη αυτό που λέω εγώ το κατάλαβες. Θεωρώ ότι όταν μιλάς για πολυπλοκότητα μιλάς για συνάρτηση με ανεξάρτητη μεταβλητή το μέγεθος εισόδου (ή κάποιο σταθερό πολλαπλάσιο).

Ο Λάμπρος λέει ότι το μέγεθος εισόδου είναι n και ότι η f(n²)=2n²+4n+4 είναι γραμμικής τάξης με τα οποία διαφωνώ. Για αυτό και ρώτησα ποιο θεωρεί μέγεθος εισόδου (και απάντησε n και όχι n² )

[dpa2006]

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

Αν θυμάμαι καλά ως την παράγραφος 5.1.4
http://edu.klimaka.gr/arxeio/nomothesia-fek/fek-1186-2015-exetastea-ylh-lykeio-klimaka.pdf
είναι η ύλη
Το συγκεκριμένο κομμάτι είναι η 5.3 Πολυπλοκότητα αλγορίθμων,άρα εκτός ύλης (διορθώστε με αν κάνω λάθος)
Είναι καθαρά Μαθηματικό Αντικείμενο,
Algorithms and Complexity Hermbet wilf
Pennsylvania University
https://www.math.upenn.edu/~wilf/AlgoComp.pdf

Αλγόριθμοι και Πολυπλοκότητα Φωτάκης Δημήτρης ΣΗΜΜΥ ΕΜΠ
http://www.corelab.ece.ntua.gr/courses/algorithms/

Ασυμπτωτικός Συμβολισμός
http://www.corelab.ece.ntua.gr/courses/algorithms/slides/03_AsymptoticNotation.pdf

Ασκήσεις στον Ασυμπτωτικό Συμβολισμό
http://www.corelab.ece.ntua.gr/courses/algorithms/problemsets/set01.pdf

Μερικές επιπλέον ασκήσεις (λυμένες) σε Αλγόριθμους και Πολυπλοκότητα

https://www.cs.auckland.ac.nz/courses/compsci220s1t/lectures/lecturenotes/GG-lectures/220exercises1.pdf

Σελ 4 έχει λυμένα παραδείγματα σε Big O notation

http://www.csc.kth.se/utbildning/kth/kurser/DD2354/algokomp10/Ovningar/Exercise1_Sol.pdf

A Gentle Introduction to Algorithms and Complexity
http://discrete.gr/complexity/

Ελπίζω να βοηθήσουν 

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

[Λάμπρος Παπαδόπουλος]

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

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

Η συνάρτηση που θα προκύψει με μεταβλητή το ακριβές μέγεθος εισόδου σίγουρα δεν θα έχει το ίδιο τύπο (δεν είμαι σίγουρος για το ποιος είναι μοιάζει να είναι  f(n)=2n+4n^1/2+4 ) αλλά μου έγραψες ότι η συνάρτηση f(n²)=2n²+4n+4 είναι γραμμική και εγώ σου απάντησα ότι δεν είναι. Απ' ότι κατάλαβα όμως από το επόμενο σχόλιό σου εννοούσες γραμμικής τάξης που όντως είναι.

Πάντως ο συμβολισμός Ο δεν αποτελεί αυστηρό όριο οπότε κάθε συνάρτηση Ο(n) είναι και Ο(n²)  (Cormen)

@dpa2006 πολύ ενδιαφέρων κατάλογος.

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

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

[evry]

Πράγματι, όμως έτσι καταστρέφουμε όλο το μάθημα, διότι αν ρωτήσουμε έναν μαθητή τι πολυπλοκότητα έχει η σειριακή αναζήτηση και αυτός απαντήσει εκθετική ή τετραγωνική ή κυβική θα είναι σωστός. Μπορεί να χρησιμοποιούμε το σύμβολο big-O , αλλά στην πραγματικότητα εννοούμε το Θ, δεν εννοούμε το Ο.
Αυτό έχει επικρατήσει γενικά στην πληροφορική, όλοι χρησιμοποιούν το Ο αλλά στην πραγματικότητα εννοούν το Θ, ή για να είμαι ακριβής το ελάχιστο άνω φράγμα (supremum) αφού σε κάποιες περιπτώσεις το Θ δεν ορίζεται (βλέπε σειριακή αναζήτηση ως το πιο κλασικό παράδειγμα που είναι O(n) και Ω(1)), αφού δεν υπάρχει πάντα tight bound.
Εμείς αυτό που ψάχνουμε είναι το Θ στην χειρότερη περίπτωση.

Πάντως ο συμβολισμός Ο δεν αποτελεί αυστηρό όριο οπότε κάθε συνάρτηση Ο(n) είναι και Ο(n²)  (Cormen)

[alkisg]

Θεωρώ ότι όταν μιλάς για πολυπλοκότητα μιλάς για συνάρτηση με ανεξάρτητη μεταβλητή το μέγεθος εισόδου (ή κάποιο σταθερό πολλαπλάσιο).

Γιώργο αυτό δεν ισχύει πάντα, π.χ. ο υπολογισμός του ν-οστού δεκαδικού ψηφίου του αριθμού π σίγουρα δεν έχει πολυπλοκότητα Ο(1), όπου 1 η είσοδος. Εκεί θα εκφράσουμε την πολυπλοκότητα με βάση τον αριθμό των ενδιάμεσων δεκαδικών ψηφίων που πρέπει να υπολογίσουμε για να φτάσουμε τελικά στο ν-οστό.

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

[Λάμπρος Παπαδόπουλος]

Πράγματι, όμως έτσι καταστρέφουμε όλο το μάθημα, διότι αν ρωτήσουμε έναν μαθητή τι πολυπλοκότητα έχει η σειριακή αναζήτηση και αυτός απαντήσει εκθετική ή τετραγωνική ή κυβική θα είναι σωστός. Μπορεί να χρησιμοποιούμε το σύμβολο big-O , αλλά στην πραγματικότητα εννοούμε το Θ, δεν εννοούμε το Ο.

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

[VAIOS]

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

[dpa2006]

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

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

Η συνάρτηση που θα προκύψει με μεταβλητή το ακριβές μέγεθος εισόδου σίγουρα δεν θα έχει το ίδιο τύπο (δεν είμαι σίγουρος για το ποιος είναι μοιάζει να είναι  f(n)=2n+4n^1/2+4 ) αλλά μου έγραψες ότι η συνάρτηση f(n²)=2n²+4n+4 είναι γραμμική και εγώ σου απάντησα ότι δεν είναι. Απ' ότι κατάλαβα όμως από το επόμενο σχόλιό σου εννοούσες γραμμικής τάξης που όντως είναι.

Πάντως ο συμβολισμός Ο δεν αποτελεί αυστηρό όριο οπότε κάθε συνάρτηση Ο(n) είναι και Ο(n²)  (Cormen)

@dpa2006 πολύ ενδιαφέρων κατάλογος.

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

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

Έχεις δίκιο,όπως το θέτεις.

[dpa2006]

Πράγματι, όμως έτσι καταστρέφουμε όλο το μάθημα, διότι αν ρωτήσουμε έναν μαθητή τι πολυπλοκότητα έχει η σειριακή αναζήτηση και αυτός απαντήσει εκθετική ή τετραγωνική ή κυβική θα είναι σωστός. Μπορεί να χρησιμοποιούμε το σύμβολο big-O , αλλά στην πραγματικότητα εννοούμε το Θ, δεν εννοούμε το Ο.
Αυτό έχει επικρατήσει γενικά στην πληροφορική, όλοι χρησιμοποιούν το Ο αλλά στην πραγματικότητα εννοούν το Θ, ή για να είμαι ακριβής το ελάχιστο άνω φράγμα (supremum) αφού σε κάποιες περιπτώσεις το Θ δεν ορίζεται (βλέπε σειριακή αναζήτηση ως το πιο κλασικό παράδειγμα που είναι O(n) και Ω(1)), αφού δεν υπάρχει πάντα tight bound.
Εμείς αυτό που ψάχνουμε είναι το Θ στην χειρότερη περίπτωση.

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

[gpapargi]

Γιώργο αυτό δεν ισχύει πάντα, π.χ. ο υπολογισμός του ν-οστού δεκαδικού ψηφίου του αριθμού π σίγουρα δεν έχει πολυπλοκότητα Ο(1), όπου 1 η είσοδος. Εκεί θα εκφράσουμε την πολυπλοκότητα με βάση τον αριθμό των ενδιάμεσων δεκαδικών ψηφίων που πρέπει να υπολογίσουμε για να φτάσουμε τελικά στο ν-οστό.

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

Είναι περίεργο και ενδιαφέρον το θέμα Άλκη. Δεν είναι 1 το μέγεθος εισόδου στον αριθμό. Είναι το πλήθος των ψηφίων. Οπότε έτσι δε βγαίνει Ο(1).
Πχ ο αλγόριθμος
Διάβασε ν
Για ι από 1 μέχρι ν
   Γράψε ι
Τέλος_επανάληψης
Έχει εκθετική πολυπλοκότητα. Το μέγεθος εισόδου είναι το πλήθος των ψηφίων δηλαδή log(ν). Έτσι έχω f(log(ν))=ν που είναι εκθετική (αν θέλεις όπου log(ν) το x θα βγει το εκθετικό).

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

[alkisg]

Γιώργο δεν νομίζω ότι θα βρεις κάπου στη βιβλιογραφία να αναφέρουν ότι η σειριακή αναζήτηση έχει εκθετική πολυπλοκότητα... κι αυτό επειδή ως βασική μονάδα εισόδου αριθμητικών δεδομένων θεωρούμε τη λέξη (word) του επεξεργαστή, όχι το bit.
Κι αυτό με τη σειρά του γίνεται επειδή τα bit κάθε λέξης επεξεργάζονται παράλληλα από την CPU σε Ο(1) με τις αντίστοιχες εντολές assembly, είτε αυτός είναι ακέραιος είτε πραγματικός.
Βέβαια για να γίνουν οι παραπάνω πολύ λογικές παραδοχές, κατά την μελέτη της πολυπλοκότητας θεωρούμε ότι τα δεδομένα μας δεν υπερβαίνουν το μέγεθος της λέξης του επεξεργαστή, και επίσης ότι δεν χρειάζεται βιβλιοθήκη αριθμών άπειρης ακρίβειας.
Επιτρέπεται όμως ο compiler να κάνει emulation λέξης μεγέθους π.χ. 64 bit σε επεξεργαστή 32 bit, δηλαδή τεχνητή αύξηση του μεγέθους λέξης, χωρίς να μας επηρεάζει στη μελέτη της πολυπλοκότητας, αφού το emulation γίνεται σε σταθερό χρόνο, άρα πάλι Ο(1).

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

Επίσης μια τελευταία παρατήρηση είναι ότι αν για κάποιο τραβηγμένο λόγο επιμέναμε ότι θέλουμε να αγνοήσουμε την αρχιτεκτονική των επεξεργαστών που είναι οργανωμένη σε λέξεις, και να αρχίσουμε να τα μετράμε όλα σε bit, τότε αυτό θα ήταν παραπλήσιο με τη χρήση βιβλιοθήκης αριθμών άπειρης ακρίβειας, και θα είχε σαν αποτέλεσμα ούτε οι βασικές πράξεις ούτε η προσπέλαση πινάκων να γίνεται πια σε Ο(1). Ούτε καν η προσπέλαση της RAM δεν θα γινόταν σε Ο(1), αφού δεν θα ήταν πια οργανωμένη σε λέξεις περιορισμένων bits. Ο απόλυτος χαμός. Θα χρειαζόμασταν διδακτορικό μόνο και μόνο για να μελετήσουμε την πολυπλοκότητα της σειριακής αναζήτησης... α πα πα!

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

Υ.Γ. ήθελα να αναφέρω ότι αντίστοιχες παραδοχές ισχύουν και για characters και για σταθερού μεγέθους strings και για structs/records, μιας και δεν αφορούν αριθμούς όλα τα προβλήματα, αλλά δεν ήμουν σίγουρος αν θα πρόσφερε ή θα έμπλεκε τη συζήτηση.

[pgrontas]

Δεν νομίζω ότι έχει σχέση οποιαδήποτε αναπαράσταση σε λέξεις κτλ. γιατί θα είναι πάντα σταθερό πολλαπλάσιο του πλήθους των bit.
Τυπικά, ο υπολογισμός της πολυπλοκότητας ενός αλγορίθμου γίνεται με βάση τον κοινά αποδεκτό φορμαλισμό του, δηλ. τις μηχανές Turing. Όταν λοιπόν λέμε μέγεθος της εισόδου εννοούμε πόσα κελιά της ταινίας θα χρειαστούν για να γράψουμε την είσοδο, όπου κάθε κελί δέχεται 1 bit.

Στην σειριακή αναζήτηση χρειάζονται cN κελιά όπου Ν το πλήθος των στοιχείων και c το πλήθος των bits που θα χρειαστούν για την κωδικοποίηση καθενός (δηλ. του μέγιστου).Στον έλεγχο του αν ένας αριθμός είναι πρώτος, γράφουμε την αναπαράσταση του ίδιου του αριθμού στο δυαδικό. Εκεί το μέγεθος της εισόδου N είναι το πλήθος των bits. Ο αλγόριθμος θα πρέπει να ελέγξει 2^Ν συνδυασμούς (τάξη μεγέθους) συμβόλων (αριθμών μέχρι το Ν) για να αποφανθεί. Η διαφορά είναι ότι στην σειριακή αναζήτηση δεν πρέπει να γράψουμε στην ταινία το Ν, γι' αυτό και δεν είναι εκθετική.

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

[tasospap]

Συγνώμη, περιμένετε να γράψουν τα παιδιά για τον φορμαλισμό της μηχανής του Turing, για την ταινία με τα κελιά  και τα σύμβολα της; 

Το παίζετε ή πράγματι σκέφτεστε ετσι;

[pgrontas]

tasospap
Προφανώς και η συζήτηση δεν αφορά τους μαθητές αλλά την καλύτερη κατανόηση από εμάς τους εκπαιδευτικούς.
Περιμένω και τη δική σου συνεισφορά