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

[gpapargi]

 

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

Εδώ θα πρέπει να αναφέρουμε κάποια πράγματα. Όταν εκφράζεις την πολυπλοκότητα σα συνάρτηση του μεγέθους εισόδου δεν το κάνεις με απόλυτη ακρίβεια. Να δώσω ένα πιστεύω γενικά αποδεκτό παράδειγμα. Διαβάζω έναν ακέραιο ν και ελέγχω αν είναι πρώτος κάνοντας όλες τις διαιρέσεις. Αυτός ο αλγόριθμος στη βιβλιογραφία θεωρείται εκθετικός. Λέω δηλαδή log(n) το πλήθος των ψηφίων και άρα έχω f(log(n))=n και θέτωντας log(n)=κ καταλήγω στο f(κ)=10^κ.
Τι έχω εδώ;
Έχω μια συνάρτηση που δίνει τα βήματα συναρτήσει του πλήθους των ψηφίων και βλέπω ότι η σχέση είναι εκθετική. Δεν έχω όμως απόλυτη ακρίβεια. Αυτό το καταλαβαίνω και διαισθητικά: ο 100 έχει ίδιο πλήθος ψηφίων με το 999 αλλά ο αλγόριθμος δεν κάνει ίδιο πλήθος βημάτων για το 100 και το 999. Και μαθηματικά βλέπω ότι βάζοντας κ=3 έχω μια τιμή (το 1000) είτε έχω σαν είσοδο το 100 είτε το 999. Δεν υπάρχει απόλυτη ακρίβεια. Αυτό το ξέρω εξαρχής. Και είναι λογικό να χάνω σε ακρίβεια αφού θέτωντας logn=κ, το κ είναι ακέραιος και άρα περιορίζομαι σε ακεραίους.
Αυτό ακριβώς είναι και το νόημα της τάξης. Με νοιάζει να δω την τάξη του αλγορίθμου δηλαδή με τι ρυθμό (σαν ποια συνάρτηση) μεγαλώνει το πλήθος των βημάτων σα συνάρτηση του μεγέθους εισόδου.
Προφανώς λοιπόν δεν μπορώ να βρω ακριβώς τα βήματα εισόδου. Θα μπορούσα να δώσω και ένα πιο χτυπητό παράδειγμα. Στη παράδειγμα με τη διαφορά 2 αριθμών μπορώ να παρακάμψω τις δυσκολίες και να βρω μια λύση. Ωστόσο αν έχω συνάρτηση σε πεπλεγμένη μορφή πχ ένα πολυόνυμο έκτου βαθμού, ή 10^n+n+n^2+log(n) εκεί δεν μπορώ να λύσω ως προς n. Αλλά δε με νοιάζει. Το ξέρω εξαρχής ότι δεν έχω απόλυτη ακρίβεια. Θέλω μόνο να δω το ρυθμό  αύξησης στο άπειρο. Έτσι στο παράδειγμα που έχω πχ
f(10^n+n+n^2+log(n))=n, θα δω τι κάνει ο κάθε όρος και τελικά θα δω ότι ο log(n) δημιουργεί εκθετική πολυπλοκότητα και θα επισκιάσει τους άλλους στο άπειρο.
Ανακεφαλαιώνοντας θέλω να πω ότι η εύρεση πολυπλοκότητας σα συνάρτηση του μεγέθους εισόδου δεν είναι μια μέθοδος για να βρεις ακριβώς το πλήθος των βημάτων. Είναι για να κατατάξεις το αλγόριθμο στους εκθετικούς, ή στους λογαριθμικούς ή στους πολυωνυμικούς κάποιου βαθμού κλπ. Πρέπει να υπάρχει κάποιος τρόπος για να κατατάξεις τους αλγορίθμους σε εκθετικού χρόνου, πολυωνυμικού χρόνου κλπ. Αυτό γίνεται με τη χρήση του μεγέθους εισόδου σαν ανεξάρτητη μεταβλητή και κοιτώντας το μεγιστοβάθμιο όρο. Αν πχ έχεις ένα δισδιάστατο πίνακα με ν^2 στοιχεία, πρέπει να μπορείς να πεις αν ο αλγόριθμος είναι τετραγωνικού ή γραμμικού χρόνου. Αυτό μπορεί να γίνει με το μέγεθος της εισόδου. Αν διαλέξεις το μήκος της γραμμής και βγάλεις ν τα βήματα, δεν μπορείς να πεις ότι είναι γραμμικού χρόνου. Ισχυρίζομαι επίσης ότι όταν αλλάζεις την ανεξάρτητη  μεταβλητή και χρησιμοποιείς μια άλλη, θα πρέπει να είναι αριθμητικό πολλαπλάσιο του πλήθους των bits έτσι ώστε ως προς οποιαδήποτε μεταβλητή ο εκθετικός να παραμένει εκθετικός και ο γραμμικός να παραμένει γραμμικός.   

[gpapargi]

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

Αυτό το είχα θίξει παραπάνω. Το γράφω κάπως πιο αναλυτικά. Μέγεθος εισόδου κανονικά είναι το πλήθος των bits εισόδου. Αντί για αυτό μπορούμε να χρησιμοποιήσουμε και κάποιο αριθμητικό πολλαπλάσιο των bits εισόδου, όπως πχ το πλήθος των χαρακτήρων, το μέγεθος λέξης, το πλήθος των ψηφίων κλπ. Είναι σαν να αλλάζω μονάδα μετρήσεως. Όπως πχ μετράω ένα μήκος σε μέτρα ή σε χιλιόμετρα. Δεν αλλάζει όμως η τάξη του αλγορίθμου η εισαγωγή της σταθεράς όσο μεγάλη και να είναι (αρκεί να είναι πεπερασμένη).
Όταν ελέγχω για το αν ο αριθμός είναι πρώτος μέγεθος εισόδου είναι το πλήθος των ψηφίων, ενώ όταν κάνω σειριακή μεταξύ αριθμών που είναι σε πίνακα χρησιμοποιώ το πλήθος των στοιχείων του πίνακα. Γιατί γίνεται αυτό;
Αυτό γίνεται γιατί όταν φανταζόμαστε να αυξάνει το μέγεθος εισόδου στο πρόβλημα της σειριακής φανταζόμαστε το πλήθος των στοιχείων να τείνει στο άπειρο και όχι το μέγεθος του κάθε αριθμού να τείνει στο άπειρο. Είμαι δηλαδή φραγμένος στο πλήθος των ψηφίων του αριθμού και έχω απειρισμό στο πλήθος τους. Αυτό είναι που εννοώ συνήθως. Δεν είναι απόλυτο να είναι έτσι.
Αν θέλουμε να τείνει στο άπειρο και το μέγεθος του κάθε αριθμού τότε πάμε σε συνάρτηση 2 ανεξάρτητων μεταβλητών. Δηλαδή αν ν το πλήθος των στοιχείων και κ το πλήθος των ψηφίων του κάθε αριθμού τότε έχω συνάρτηση της μορφής f(ν,κ). Δηλαδή το αντιμετωπίζω περίπου  σαν πίνακα δυο διαστάσεων με αριθμό γραμμών ν και αριθμό στηλών κ.  Όχι όμως τετραγωνικό γιατί θέλω να έχω ανεξάρτητη αύξηση σε κάθε διάσταση.
Αν έχω κάποιο μέγιστο μήκος σε κάθε στοιχείο του πίνακα, ας είναι και 10^9 bits τότε έχω αριθμητικό πολλαπλάσιο και άρα o  απειρισμός είναι μόνο στο πλήθος των στοιχείων. Δεν αλλάζει η τάξη όσο μεγάλη και να είναι η λέξη μου αρκεί να είναι πεπερασμένη. Προσοχή σε αυτό: οσοδήποτε μεγάλος αριθμός και να υπάρχει στο σύνολο των bits της λέξης είναι πεπερασμένος και λειτουργεί σα σταθερά. Δεν είναι απειρισμός και δεν αλλάζει την γραμμική τάξη.

[Diotima]

Γιώργο εγώ συμφωνώ ότι πρέπει να ακολουθούμε το μαθηματικό ορισμό και να μιλάμε με βάση αυτόν. Έχει σημασία να εννοούμε το ίδιο πράγμα όταν μιλάμε για Ο(1) και Ο(ν). Καταλαβαίνω τους λόγους που διαφωνεί ο Άλκης, στην πραγματική ζωή δεν υπάρχει τίποτα το άπειρο και τα πάντα είναι πεπερασμένα, μπορεί στην εφαρμογή να ενδιαφέρει η συμπεριφορά της συνάρτησης ακόμα κι αν έχει τάξη Ο(1).
Όμως η ασυμπτωτική ανάλυση ενός αλγορίθμου με βάση τη θεωρία της πολυπλοκότητας δε λαμβάνει υπόψη την εφαρμογή στην πραγματική ζωή, τα μαθηματικά, ειδικά όταν μιλάνε για μεγέθη που τείνουν στο άπειρο δεν έχουν σκοπό να εξετάσουν τα πράγματα με βάση την πραγματικότητα. Η έννοια του ορίου στο άπειρο είναι κατά τη γνώμη μου ίσως η πιο δύσκολη μαθηματική έννοια και θα το πω μια και το έφερε η κουβέντα, θεωρώ λάθος που τα παιδιά της Γ' Λυκείου δίνουν πανελλαδικές εξεταζόμενα στην ανάλυση που έχει κεντρική έννοια τη έννοια του ορίου (όρια, συνέχεια, παράγωγοι, ολοκληρώματα κ.τ.λ.) ενώ δυσκολεύονται πολύ να αναλύσουν ένα πρόβλημα της πραγματικής ζωής.

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

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

Άρα στα πλαίσια της σχολικής ύλης, της σειριακής αναζήτησης, της ταξινόμησης, της διαφοράς δύο αριθμών α-β κλπ, προφανώς και είναι λογικό να χρησιμοποιούμε unit time και uniform cost model.

Συμφωνώ απόλυτα και χαίρομαι που αυτό ξεκαθαρίστηκε, νομίζω ότι πρέπει να είναι αποδεκτό από όλους.
Να πω εδώ, ότι το πρόβλημα 2 που όρισα στην αρχική μου ανάρτηση πάνω στον αλγόριθμο που πρότεινε ο Γιώργος σέβεται αυτόν τον κανόνα, γιατί μπορεί η συνάρτηση πολυπλοκότητας να εκφράζεται τελικά ως f(m)=2^m, όπου m=logn, δηλαδή μέσω των ψηφίων του αριθμού n και να είναι εκθετική ως προς αυτό, αλλά το κόστος κάθε βασικής πράξης παραμένει 1, απλά το πρόβλημα μετράει το πλήθος των βασικών πράξεων που γίνονται όχι κάθε φορά που το n αυξάνεται κατά 1, αλλά κάθε φορά που διπλασιάζεται αν αναφερόμαστε στο δυαδικό σύστημα, δεκαπλασιάζεται στο δεκαδικό κ.τ.λ. οπότε η συνάρτηση με τη γραφική της παράσταση δείχνει τη μεταβολή του πλήθους των πράξεων όταν συμβαίνει αυτή η μεταβολή στον αριθμό.
Η διαισθητική σημασία του αλγορίθμου βέβαια δεν το δείχνει αυτό, απλά ο αλγόριθμος σου επιτρέπει να ορίσεις ένα τέτοιο πρόβλημα πολυπλοκότητας και μπορείς φυσικά να το κάνεις γιατί μπορεί αυτό να σε ενδιαφέρει να μελετήσεις.

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

[alkisg]

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

Έχω μια συνάρτηση που δίνει τα βήματα συναρτήσει του πλήθους των ψηφίων και βλέπω ότι η σχέση είναι εκθετική. Δεν έχω όμως απόλυτη ακρίβεια.

Βρε Γιώργο έχω ήδη δώσει αντιπαράδειγμα ότι δεν είναι εκθετική με βάση το πλήθος bit της εισόδου. Αλλάζω λίγο την "Γράψε ι" σε "Γράψε α-β" μόνο και μόνο για να δώσω καλύτερο παράδειγμα:
Διάβασε α, β
Για ι από α μέχρι β
  Γράψε α-β
Τέλος_επανάληψης

Πάρε ένα όσο μεγάλο Χ θες. Να τείνει στο άπειρο.
Μετά δώσε στον αλγόριθμο ως είσοδο: α=Χ, και β=Χ. Έδωσες άπειρα bit στην είσοδο.
Ο αλγόριθμος θα κάνει ακριβώς μία επανάληψη. Θα κάνει και ακριβώς μία αφαίρεση. Και θα εμφανίσει ακριβώς ένα νούμερο, το 0.

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

Δεν προχωράω παρακάτω μέχρι να ξεκαθαρίσουμε ότι έχω δίκιο σ' αυτό το κομμάτι, ή να μου εξηγήσετε πώς είναι δυνατόν να της δίνω άπειρα bit εισόδου, να κάνω μία μόνο πράξη, να παίρνω μόνο ένα 0 για έξοδο, και αυτό να το ονομάζετε εκθετική πολυπλοκότητα!

[gpapargi]

Γράφω κάτι για τα cost models που είχα ήδη πληκτρολογήσει και μετά θα δω το τελευταίο σου μήνυμα Άλκη.
Και για εγώ θεωρώ Ο(1) το κόστος για να γίνει η πράξη στον ακέραιο όσο μεγάλο και να είναι το μήκος  αρκεί να είναι πεπερασμένο. Στο άπειρο δεν ισχύει αυτό.
Στη σελίδα της Wikipedia το logarithmic cost model δίνει μια πράξη για κάθε bit εισόδου. Εγώ δεν κάνω  κάτι τέτοιο. Συγκεκριμένα δηλαδή σε μια διαίρεση δίνει κόστος ανάλογο με το πλήθος των bits των αριθμών. Εγώ το μετράω για μια πράξη. Αλλά το πλήθος των επαναλήψεων είναι που εκφράζω σαν συνάρτηση των bits εισόδου. Uniform cost εφαρμόζω

[itt]

Πλέον έχω ένα σωρό διαφωνίες, αλλά νομίζω θα πρέπει να είμαι λακωνικός και να εστιάσω μία μία σε μερικές πολύ σημαντικές λεπτομέρειες, γιατί αν δεν πιάσουμε κάποιες βάσεις που να συμφωνούμε, δεν θα προχωρήσει η συζήτηση.
Βρε Γιώργο έχω ήδη δώσει αντιπαράδειγμα ότι δεν είναι εκθετική με βάση το πλήθος bit της εισόδου. Αλλάζω λίγο την "Γράψε ι" σε "Γράψε α-β" μόνο και μόνο για να δώσω καλύτερο παράδειγμα:
Διάβασε α, β
Για ι από α μέχρι β
  Γράψε α-β
Τέλος_επανάληψης

Πάρε ένα όσο μεγάλο Χ θες. Να τείνει στο άπειρο.
Μετά δώσε στον αλγόριθμο ως είσοδο: α=Χ, και β=Χ. Έδωσες άπειρα bit στην είσοδο.
Ο αλγόριθμος θα κάνει ακριβώς μία επανάληψη. Θα κάνει και ακριβώς μία αφαίρεση. Και θα εμφανίσει ακριβώς ένα νούμερο, το 0.

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

Δεν προχωράω παρακάτω μέχρι να ξεκαθαρίσουμε ότι έχω δίκιο σ' αυτό το κομμάτι, ή να μου εξηγήσετε πώς είναι δυνατόν να της δίνω άπειρα bit εισόδου, να κάνω μία μόνο πράξη, να παίρνω μόνο ένα 0 για έξοδο, και αυτό να το ονομάζετε εκθετική πολυπλοκότητα!

Κάτσε ρε συ, την περιπλοκότητα Ω (ή έστω την Ο) δεν συζητάτε τόση ώρα; Αυτό που γράφεις εσύ δεν είναι ούτε καν η μέση περίπτωση. Επίσης δεν έχει καν νόημα, γιατί μιλάμε για ασυμπτωτική ανάλυση, άρα όρια, άρα το να πεις ότι το a = infinite δεν νομίζω ότι στέκει μαθηματικά.

[gpapargi]

Πλέον έχω ένα σωρό διαφωνίες, αλλά νομίζω θα πρέπει να είμαι λακωνικός και να εστιάσω μία μία σε μερικές πολύ σημαντικές λεπτομέρειες, γιατί αν δεν πιάσουμε κάποιες βάσεις που να συμφωνούμε, δεν θα προχωρήσει η συζήτηση.
Βρε Γιώργο έχω ήδη δώσει αντιπαράδειγμα ότι δεν είναι εκθετική με βάση το πλήθος bit της εισόδου. Αλλάζω λίγο την "Γράψε ι" σε "Γράψε α-β" μόνο και μόνο για να δώσω καλύτερο παράδειγμα:
Διάβασε α, β
Για ι από α μέχρι β
  Γράψε α-β
Τέλος_επανάληψης

Πάρε ένα όσο μεγάλο Χ θες. Να τείνει στο άπειρο.
Μετά δώσε στον αλγόριθμο ως είσοδο: α=Χ, και β=Χ. Έδωσες άπειρα bit στην είσοδο.
Ο αλγόριθμος θα κάνει ακριβώς μία επανάληψη. Θα κάνει και ακριβώς μία αφαίρεση. Και θα εμφανίσει ακριβώς ένα νούμερο, το 0.

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

Δεν προχωράω παρακάτω μέχρι να ξεκαθαρίσουμε ότι έχω δίκιο σ' αυτό το κομμάτι, ή να μου εξηγήσετε πώς είναι δυνατόν να της δίνω άπειρα bit εισόδου, να κάνω μία μόνο πράξη, να παίρνω μόνο ένα 0 για έξοδο, και αυτό να το ονομάζετε εκθετική πολυπλοκότητα!

Όπως πάντα αυτές η κουβέντες είναι τρομερές  και μου είχαν λείψει

Στην ανάλυση που έκανα δε χρησιμοποίησα ακέραια μέρη που θα έδινε πιο μεγάλη ακρίβεια. Θα απαντήσω κάπως πιο χοντρικά γιατί ελπίζω ότι θα σε πείσω.
Έχω βγάλει κάτι σαν f(n)=10^(n/x) όπου x θετική σταθερά. Όσο μεγάλη και να είναι η x δεν μπορείς να πεις ότι τείνει στο άπειρο γιατί είναι σταθερά. Η f(n) τείνει πάντα προς το άπειρο για κάθε συγκεκριμένη τιμή του x που θα βάλεις. Απλά αλλάζεις τον εκθέτη και έχει μια πιο αργή εκθετική δηλαδή που πάει στο άπειρο πιο αργά. Αλλά είναι εκθετική. Θα ξεπεράσει οποιαδήποτε πολυωνυμική αν αφήσουμε το ν να ανέβει αρκετά.
Μια εκθετική μπορεί να δώσει και πολύ μικρές τιμές. Αν πχ βάλει όπου n το μηδέν έχει 10^0 που κάνει 1. Δηλαδή δε σημαίνει ότι η εκθετική θα δώσει μόνο μεγάλες τιμές. Αν βάλεις μικρό όρισμα θα πάρεις μικρή τιμή. Με πλάτος διαστήματος 0 θα πάρεις μια επανάληψη από την εκθετική. 

[dpa2006]

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

[Diotima]

Λοιπόν, νομίζω ότι συνειδητοποίησα για ποιο λόγο υπάρχουν οι διαφωνίες. Δε νομίζω ότι διαφωνούμε στο uniform cost model και το unit time, οι διαφωνίες προκύπτουν γιατί θεωρούμε την αναπαράσταση της εισόδου με άλλο τρόπο.

Δηλαδή, όταν αντιλαμβανόμαστε έναν ακέραιο με βάση την αριθμητική του ποσότητα, τότε θεωρούμε την αναπαράσταση του σε ένα σύστημα αρίθμησης με βάση το 1, το λεγόμενο unary numeral system, https://en.wikipedia.org/wiki/Unary_numeral_system.

Οπότε, για είσοδο τον ακέραιο ν, χρειαζόμαστε ν bits (ή ψηφία)για να τον αναπαραστήσουμε, δηλαδή το πλήθος των bits εισόδου που λέει ο Γιώργος είναι ν.

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

Γι αυτό στη μία περίπτωση παίρνουμε γραμμική και στην άλλη εκθετική πολυπλοκότητα.
Χρησιμοποίησα τον όρο "bits εισόδου" αντί για πλήθος των ψηφίων του αριθμού σε οποιοδήποτε σύστημα αρίθμησης.
Άρα στην ουσία μπορούμε να μιλάμε για πλήθος των "bits εισόδου" και στις δύο περιπτώσεις, σημασία έχει σε ποιο σύστημα θεωρούμε την αναπαράσταση του ακεραίου ν.
Προφανώς, αν αλλάξω την αναπαράσταση του αριθμού αλλάζει και η πολυπλοκότητα.
Μπορεί εσείς αυτά να τα έχετε συνειδητοποιήσει, αλλά εγώ τώρα τα συνειδητοποιώ καλά και βλέπω πόσο μεγάλη σημασία έχουν στον υπολογισμό της πολυπλοκότητας.

[alkisg]

Κάτσε ρε συ, την περιπλοκότητα Ω (ή έστω την Ο) δεν συζητάτε τόση ώρα; Αυτό που γράφεις εσύ δεν είναι ούτε καν η μέση περίπτωση. Επίσης δεν έχει καν νόημα, γιατί μιλάμε για ασυμπτωτική ανάλυση, άρα όρια, άρα το να πεις ότι το a = infinite δεν νομίζω ότι στέκει μαθηματικά.

Εγώ δεν αναλύω την πολυπλοκότητα, ίσα ίσα λέω ότι δεν ορίζεται η πολυπλοκότητα ως προς τα bits της εισόδου. Πώς να δώσω μέση τιμή από κάτι που δεν ορίζεται;
Το πλήθος των bits log(α-β) που προσπαθεί να υπολογίσει ο Γιώργος δεν ορίζεται όταν και το α και το β τείνουν στο άπειρο:

The indeterminate forms typically considered in the literature are denoted 0/0, ∞/∞, 0 × ∞, ∞ − ∞, 00, 1∞ and ∞0.

Αυτό που λες ότι το "a = infinite δεν νομίζω ότι στέκει μαθηματικά", εννοείται ότι πάντα μιλάμε για όρια, και θεωρητικά πρέπει πάντα να γράφουμε την φράση "τείνει στο άπειρο" αντί για "άπειρο", αλλά για χάρη συντομίας συνηθίζεται πολλές φορές να παραλείπουμε τη λέξη "τείνει", όπως βλέπεις και από το παραπάνω quote της wikipedia. Μπορείς να την προσθέτεις νοητικά όπου έχει παραληφθεί.

[alkisg]

Δηλαδή, όταν αντιλαμβανόμαστε έναν ακέραιο με βάση την αριθμητική του ποσότητα, τότε θεωρούμε την αναπαράσταση του σε ένα σύστημα αρίθμησης με βάση το 1, το λεγόμενο unary numeral system, https://en.wikipedia.org/wiki/Unary_numeral_system.

Diotima όχι μην μπλέκουμε τα πράγματα, κανείς μας δεν μίλησε για μοναδιαίο σύστημα αρίθμησης. Στα μοναδιαία συστήματα, ένας π.χ. 64 bit αριθμός χρειάζεται 18446744073709551616 ψηφία για την αναπαράστασή του, και άρα κανένας σύγχρονος Η/Υ δεν θα χωρούσε ούτε μία μεταβλητή, πόσο μάλλον να κάνει πράξεις με αυτήν.
Επίσης, το πρόβλημα των πρώτων (primary) αριθμών στο μοναδιαίο σύστημα αρίθμησης είναι πολυωνυμικό και όχι εκθετικό ως προς τα bits εισόδου, κι ο Γιώργος μιλούσε για εκθετική πολυπλοκότητα.

[alkisg]

Όπως πάντα αυτές η κουβέντες είναι τρομερές  και μου είχαν λείψει

Κι εμένα! Έχασα τον μεσημεριανό μου ύπνο περιμένοντας την απάντησή σου!

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

Είπες ότι χρησιμοποιείς uniform cost model αλλά μετράς την είσοδο σε bits αντί για units.
Θεωρώ ότι αυτό είναι το βασικό πρόβλημα. Το μέτρημα σε bits γίνεται στο logarithmic μοντέλο. Στο uniform μετράμε το μέγεθος της εισόδου υποχρεωτικά σε units.
Αν πας να μετρήσεις την είσοδο με bits στο uniform, τότε όλοι οι γραμμικοί αλγόριθμοι βγαίνουν εκθετικοί κλπ, προκαλείται το χάος που βλέπουμε στο παρόν θέμα!

Γι' αυτό και η σειριακή αναζήτηση δεν αναφέρεται στην βιβλιογραφία με εκθετική πολυπλοκότητα, γιατί μετράνε την είσοδο σε units και χρησιμοποιούν uniform μοντέλο.
Γι' αυτό ο υπολογισμός πρώτων αναφέρεται με εκθετική, γιατί μετράνε την είσοδο σε bits και χρησιμοποιούν logarithmic μοντέλο.

Συμφωνούμε ως εδώ;

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

[gpapargi]

Πριν από όλα θα πρέπει να επιβεβαιώσουμε ότι εννοούμε το ίδιο πράγμα λέγοντας uniform και logarithmic cost models. Αυτό που καταλαβαίνω εγώ από τη Wikipedia είναι ότι μιλάμε για το πόσα βήματα μετράει σε κάθε πράξη. Έτσι αν έχω να προσθέσω 2 αριθμούς με 10 bits το uniform μετράει μια πράξη όλη την πρόσθεση, ενώ το logarithmic μετράει 10 πράξεις (που είναι ο λογαρίθμος του αριθμού που δίνεται σαν είσοδο).
Εγώ μετράω μια πράξη. Αλλά αυτό δε σημαίνει ότι δε θα βγάλω την πολυπλοκότητα με βάση τα bits ή κάποια πολλαπλάσιό τους. Όταν λέω ότι έχω εκθετική πολυπλοκότητα εννοώ ότι έχω εκθετικό πλήθος διαιρέσεων που μετράει η κάθε μια για 1 βήμα. Δεν εννοώ ότι έχω γραμμικά πολλές και προκύπτει η εκθετική πολυπλοκότητα επειδή μετράω πολλά βήματα στην κάθε μια.
Με άλλα λόγια για να είμαι εντάξει θα πρέπει να κάνω τα εξής:
Να βγάλω εκθετικά πολλές διαιρέσεις ως προς το σύνολο των ψηφίων (που είναι πολλαπλάσιο των bits εισόδου) μετρώντας την κάθε μια για 1 βήμα.
Επίσης θα πρέπει να βγάλω γραμμικά πολλές συγκρίσεις στη σειριακή μετρώντας για κάθε μια σύγκριση 1 βήμα. Εδώ θα πρέπει να ξεκαθαρίσω ότι ο πίνακας έχει αριθμούς  που το πλήθος των ψηφίων τους (και άρα και των bits) είναι φραγμένο. Όταν λέω γραμμικά πολλές συγκρίσεις εννοώ ως προς τα bits εισόδου ή το πλήθος ψηφίων. Το κρίσιμο σημείο είναι ότι ο απειρισμός είναι ως προς το πλήθος των στοιχείων του πίνακα ενώ το πλήθος των ψηφίων (άρα και των bits) σε κάθε αριθμό είναι φραγμένο. Άρα όταν έχω ν στοιχεία στον πίνακα και κ bits για κάθε στοιχείο του πίνακα έχω είσοδο μεγέθους κ*ν. Το κ δεν επηρεάζει την τάξη.

[Diotima]

Diotima όχι μην μπλέκουμε τα πράγματα, κανείς μας δεν μίλησε για μοναδιαίο σύστημα αρίθμησης. Στα μοναδιαία συστήματα, ένας π.χ. 64 bit αριθμός χρειάζεται 18446744073709551616 ψηφία για την αναπαράστασή του, και άρα κανένας σύγχρονος Η/Υ δεν θα χωρούσε ούτε μία μεταβλητή, πόσο μάλλον να κάνει πράξεις με αυτήν.
Επίσης, το πρόβλημα των πρώτων (primary) αριθμών στο μοναδιαίο σύστημα αρίθμησης είναι πολυωνυμικό και όχι εκθετικό ως προς τα bits εισόδου, κι ο Γιώργος μιλούσε για εκθετική πολυπλοκότητα.

Δεν έγραψα ότι στους Η/Υ η αναπαράσταση γίνεται με το μοναδιαίο σύστημα Άλκη, αυτό που είπα είναι ότι όταν αντιλαμβανόμαστε αριθμητικά μία ακέραια ποσότητα τότε ο αριθμός π.χ 7=1+1+1+1+1+1+1 στο μοναδιαίο και θέλουμε 7 το πλήθος ψηφία για να τον αναπαραστήσουμε, στο δυαδικό 7=1*2^2+1*2^1+1*2^0 και θέλουμε 3 ψηφία και στο δεκαδικό 7= 7*10^0 ένα μόνο ψηφίο. Τον αριθμό σαν αριθμητική ποσότητα τον καταλαβαίνουμε με βάση το 1.

Πριν από όλα θα πρέπει να επιβεβαιώσουμε ότι εννοούμε το ίδιο πράγμα λέγοντας uniform και logarithmic cost models. Αυτό που καταλαβαίνω εγώ από τη Wikipedia είναι ότι μιλάμε για το πόσα βήματα μετράει σε κάθε πράξη. Έτσι αν έχω να προσθέσω 2 αριθμούς με 10 bits το uniform μετράει μια πράξη όλη την πρόσθεση, ενώ το logarithmic μετράει 10 πράξεις (που είναι ο λογαρίθμος του αριθμού που δίνεται σαν είσοδο).

Κι εγώ έτσι νόμιζα αλλά δε νομίζω πλέον ότι λέει αυτό, για αυτό παραθέτω τους ορισμούς από το wikipedia:

the uniform cost model, also called uniform-cost measurement (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved

the logarithmic cost model, also called logarithmic-cost measurement (and variations thereof), assigns a cost to every machine operation proportional to the number of bits involved

Τόνισα με bold εκεί που νομίζω ότι γίνεται το λάθος κατανόησης. Το "a cost" δε σημαίνει "constant cost", όπως στην πρώτη περίπτωση. Αυτό που καταλαβαίνω είναι ότι το λογαριθμικό μοντέλο εκχωρεί ένα (κάποιο) κόστος σε κάθε λειτουργία μηχανής ανάλογα με τον αριθμό των bits που εμπλέκονται. Το ανάλογα μάλλον δεν το θεωρεί με τη μαθηματική αναλογία, διαφορετικά θα έλεγε "σταθερό κόστος", αλλά με την έννοια του "σε σχέση" με τον αριθμό των bits που εμπλέκονται.

Δηλαδή, όσον αφορά την πολυπλοκότητα, όταν θεωρώ το κόστος με βάση τα bits εισόδου συσχετίζω το κόστος της μηχανής με το πλήθος των bits εισόδου, άρα χρησιμοποιώ λογαριθμικό μοντέλο. Π.χ. στον αλγόριθμο που πρότεινες Γιώργο και έγραψα εγώ τη συνάρτηση f(m)=2^m όπου m=logn, αν ζωγραφίσω τη γραφική παράσταση στον οριζόντιο άξονα θα αυξάνω κατά 1 τα bits και η συνάρτηση θα μου δίνει στον κάθετο άξονα το πλήθος των πράξεων σε σχέση με το πλήθος των bits εισόδου.

Το uniform cost model μάλλον μου "απαγορεύει" να εκφράσω έτσι τη συνάρτηση, άσχετα αν το input γίνεται σε bits. Με τα μαθηματικά φυσικά μπορώ και το κάνω.
Δεν ξέρω αν τα κατάλαβα καλά, αυτό νομίζω θέλει να πει ο Άλκης, περιμένω απάντηση.

[gpapargi]

Κι εγώ έτσι νόμιζα αλλά δε νομίζω πλέον ότι λέει αυτό, για αυτό παραθέτω τους ορισμούς από το wikipedia:

the uniform cost model, also called uniform-cost measurement (and similar variations), assigns a constant cost to every machine operation, regardless of the size of the numbers involved

the logarithmic cost model, also called logarithmic-cost measurement (and variations thereof), assigns a cost to every machine operation proportional to the number of bits involved

Τόνισα με bold εκεί που νομίζω ότι γίνεται το λάθος κατανόησης. Το "a cost" δε σημαίνει "constant cost", όπως στην πρώτη περίπτωση. Αυτό που καταλαβαίνω είναι ότι το λογαριθμικό μοντέλο εκχωρεί ένα (κάποιο) κόστος σε κάθε λειτουργία μηχανής ανάλογα με τον αριθμό των bits που εμπλέκονται. Το ανάλογα μάλλον δεν το θεωρεί με τη μαθηματική αναλογία, διαφορετικά θα έλεγε "σταθερό κόστος", αλλά με την έννοια του "σε σχέση" με τον αριθμό των bits που εμπλέκονται.

Χρεώνει ένα σταθερό κόστος για κάθε ένα bit του αριθμού που εμπλέκεται στην πράξη. Άρα τελικά το συνολικό κόστος που χρεώνει σε όλη την πράξη είναι ανάλογο του συνολικού αριθμού των bits του αριθμού που συμμετέχει στην πράξη. Λέγεται λογαριθμικό μοντέλο γιατί το πλήθος των bits του αριθμού είναι ο λογάριθμος του αριθμού.
Αυτό καταλαβαίνω εγώ.
Αλλά το βασικό είναι ότι μιλάει για το πλήθος των βημάτων που χρεώνει σε κάθε πράξη πχ τη διαίρεση που μας ενδιαφέρει. Δε μιλάει για το πλήθος των διαιρέσεων που βγάζω εγώ εκθετικό ως προς τα bits εισόδου (ή το πλήθος των ψηφίων). Μπορώ να βγάλω εκθετικό πλήθος διαιρέσεων μετρώντας κάθε μια για 1 μόνο βήμα.
Κάπου στο μέγεθος εισόδου και στην έκφραση των βημάτων ως προς αυτό υπάρχει η παρεξήγηση νομίζω εγώ. Δεν ξέρω αν είναι αποδεκτό ότι το f(log(k))=k σημαίνει ότι f(k)=10^k