Να πω και μια άλλη σκέψη σχετικά με το μέγεθος των τύπων δεδομένων, που ίσως διευκολύνει ακόμα περισσότερο το ξεκαθάρισμα του θέματος;
Στο παραπάνω παράδειγμα είχαμε δύο ακεραίους και προσπαθούσατε να συνδέσετε την πολυπλοκότητα με βάση το μέγεθος της εισόδου σε bit.
Το μέγεθος της εισόδου όμως ήταν πάντα 2 ακέραιοι και δεν μετριόταν σε bit αλλά σε ακεραίους (words, λέξεις κλπ).
Ξέρω ότι κάποιοι έχουν αντίρρηση στην παραπάνω φράση μου. Ελπίζω με το παρόν μήνυμα να τους πείσω.
Την ίδια φράση την μεταφέρω στη σειριακή αναζήτηση, όπου συμφωνείτε ότι έχει γραμμική πολυπλοκότητα.
Δηλαδή θα πάω να εφαρμόσω στην σειριακή αναζήτηση αυτό που προσπαθήσατε να εφαρμόσετε στο πρόβλημα α-β.
Και ρωτάω: τι γίνεται όταν ο τύπος δεδομένων στη σειριακή αναζήτηση μεγαλώνει; Όταν οι αριθμοί που έχουμε αποθηκευμένους στον πίνακα και το κλειδί αναζήτησης τείνουν στο άπειρο;
Απαντώ:
Η είσοδος μετρημένη σε bit, απειρίζεται, ακόμα κι αν έχουμε π.χ. μόνο 100 αριθμούς στον πίνακα, αφού κάθε αριθμός έχει άπειρα bits.
Η είσοδος μετρημένη σε ακεραίους εξακολουθεί να εκφράζεται με το Ν που είναι ο αριθμός των ακεραίων του πίνακα.
Την πολυπλοκότητα την μετράμε θεωρώντας ότι οι πράξεις με τον τύπο που επιλέξαμε είναι πάντα Ο(1).
Το μέγεθος του ακεραίου το επιλέγουμε είτε θεωρώντας ότι είναι "επαρκής" όπως λέω εγώ, είτε με βάση την "μεγαλύτερη είσοδο" όπως λέει ο Παναγιώτης, αυτό είναι λεπτομέρεια.
Έτσι η πολυπλοκότητα της σειριακής αναζήτησης είναι πάντα Ο(Ν) όσο μεγάλος κι αν είναι ο τύπος δεδομένων μας.
Σ' αυτό το παράδειγμα λοιπόν, το μέγεθος της εισόδου είναι σημαντικό.
Αλλά δεν είναι καθόλου σημαντικό το μέγεθος της εισόδου σε bit, γιατί εξισορροπείται σε σχέση με την παραδοχή ότι οι πράξεις των ακεραίων γίνονται σε Ο(1), και έτσι τα bits των ακεραίων δεν αναφέρονται καθόλου ως ανεξάρτητη μεταβλητή κατά τον καθορισμό της πολυπλοκότητας.
edit: Αν θέλουμε και επίσημους όρους για τα παραπάνω, η
https://en.wikipedia.org/wiki/Analysis_of_algorithms τα αναφέρει ως:
"unit time", όταν θεωρούμε ότι οι πράξεις μεταξύ ακεραίων κοστίζουν Ο(1),
"uniform cost model", όταν μετράμε την πολυπλοκότητα χρησιμοποιώντας unit time,
"logarithmic cost model", όταν μετράμε τα πάντα με βάση τα bit και άρα ακόμα και οι βασικές πράξεις ΔΕΝ γίνονται σε Ο(1) (αυτό που έλεγα για τη βιβλιοθήκη αριθμών άπειρης ακρίβειας). "The latter is more cumbersome to use, so it's only employed when necessary, for example in the analysis of arbitrary-precision arithmetic algorithms, like those used in cryptography."
Άρα στα πλαίσια της σχολικής ύλης, της σειριακής αναζήτησης, της ταξινόμησης, της διαφοράς δύο αριθμών α-β κλπ, προφανώς και είναι λογικό να χρησιμοποιούμε unit time και uniform cost model.