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

[alkisg]

Στην σειριακή αναζήτηση χρειάζονται cN κελιά όπου Ν το πλήθος των στοιχείων και c το πλήθος των bits που θα χρειαστούν για την κωδικοποίηση καθενός (δηλ. του μέγιστου).

Παναγιώτη (και Γιώργο) δεν είμαι σίγουρος αν τελικά συμφωνούμε ή διαφωνούμε στην παρακάτω πρόταση:
Το μέγεθος c του βασικού τύπου δεδομένων μας (ομάδα κελιών / word / character / struct / whatever) κατά τον υπολογισμό της πολυπλοκότητας θεωρείται σταθερό, οι βασικές πράξεις πάνω τους κοστίζουν Ο(1), και έτσι δεν αναφερόμαστε καθόλου στο c.
Για παράδειγμα, η πολυπλοκότητα της σειριακής αναζήτησης, όπως αναφέρεται στη βιβλιογραφία, είναι Ο(Ν) και όχι Ο(c*N).

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

Σχετικά με το:
> Η διαφορά είναι ότι στην σειριακή αναζήτηση δεν πρέπει να γράψουμε στην ταινία το Ν
τα Ν στοιχεία της εισόδου (όπως και το στοιχείο κλειδί) δεν έχουν μέγεθος c το καθένα; Δεν γράφονται κι αυτά στην ταινία; Αν μετράς το c κατά την εκτύπωση των Ν πρώτων φυσικών αριθμών, πρέπει να το μετράς και στη σειριακή.

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

[pgrontas]

Παναγιώτη (και Γιώργο) δεν είμαι σίγουρος αν τελικά συμφωνούμε ή διαφωνούμε στην παρακάτω πρόταση:
Το μέγεθος c του βασικού τύπου δεδομένων μας (ομάδα κελιών / word / character / struct / whatever) κατά τον υπολογισμό της πολυπλοκότητας θεωρείται σταθερό, οι βασικές πράξεις πάνω τους κοστίζουν Ο(1), και έτσι δεν αναφερόμαστε καθόλου στο c.
Για παράδειγμα, η πολυπλοκότητα της σειριακής αναζήτησης, όπως αναφέρεται στη βιβλιογραφία, είναι Ο(Ν) και όχι Ο(c*N).

Φυσικά και συμφωνούμε. Έτσι κι αλλιως οι σταθερες δεν εχουν καμία σημασία.

Σχετικά με το:
> Η διαφορά είναι ότι στην σειριακή αναζήτηση δεν πρέπει να γράψουμε στην ταινία το Ν
τα Ν στοιχεία της εισόδου (όπως και το στοιχείο κλειδί) δεν έχουν μέγεθος c το καθένα; Δεν γράφονται κι αυτά στην ταινία; Αν μετράς το c κατά την εκτύπωση των Ν πρώτων φυσικών αριθμών, πρέπει να το μετράς και στη σειριακή.

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

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

Και κάτι άσχετο, αλλά και σχετικό:
Το 2010 στο θερινό σχολείο για εκπαιδευτικούς πληροφορικής που είχε διοργανώσει ο Ιωσήφ Σηφάκης, είχε επιχειρηματολογήσει ότι πριν τη μύηση στους αλγόριθμους οι μαθητές θα έπρεπε να εισαχθούν στα πεπερασμένα αυτόματα, με τα οποία θα σχεδίαζαν βασικές καθημερινές ενέργειες μέσω των μεταβάσεων από τις διάφορες κατάστασεις (αν θυμάμαι καλά είχε αναφέρει το ασανσερ και το φανάρι), χωρίς φυσικά να αναφερθεί η υπόλοιπη θεωρία που μαθαίνουμε στο πανεπιστήμιο. Από αυτό συμπεραίνει κανείς τουλάχιστον το ότι δεν πρέπει να είμαστε βιαστικοί πριν απορρίψουμε τα διάφορα μοντέλα που υπάρχουν στην Πληροφορική ως ακατάλληλα για διδασκαλία.

[alkisg]

Δηλαδή το "διαβάστε Ν αριθμούς και ένα κλειδί Κ και μετά κάντε σειριακή αναζήτηση"
έχει διαφορετική πολυπλοκότητα από το "έχουμε ήδη διαβασμένους τους Ν αριθμούς και το Κ, κάντε μόνο σειριακή αναζήτηση";

Δεν είναι και τα δύο Ο(Ν);

[pgrontas]

Και τα δύο έχουν Ο(Ν) φυσικά.

Όμως το ψάξε κάποιον αριθμό από όλους τους αριθμους με N bits έχει διαφορετική (εκθετική) από τα παραπάνω.

[gpapargi]

Δεν είπα ποτέ ότι η σειριακή αναζήτηση έχει εκθετική πολυπλοκότητα. Αυτό που είπα είναι ότι εκθετική πολυπλοκότητα έχει το
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης

Αν ο αριθμός  ν είναι πχ 999 με τρεις μόνο χαρακτήρες εισόδου (τα 3 ψηφία του αριθμού) αναγκάστηκα να κάνω 10^3 επαναλήψεις.
Αντίθετα αν έχω διαβάσει 10^3 διαφορετικούς αριθμούς και κάνω σε αυτούς σειριακή έχω 10^3 επαναλήψεις.
Και στις 2 περιπτώσεις έχω ίδιο πλήθος επαναλήψεων αλλά το μέγεθος εισόδου είναι πολύ διαφορετικό. Η κωδικοποίηση δεν έχει σημασία. Οι σταθερές δεν αλλάζουν την τάξη.

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

[alkisg]

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

Συνεχίζουμε:
Επόμενη ερώτησή μου είναι, γιατί το "999" να θεωρείται μεγαλύτερη είσοδος από το "99".
Εσύ θα πεις ότι το ένα έχει 3 ψηφία και το άλλο 2.
Εγώ θα πω ότι και τα δύο είναι μία λέξη, ένας ακέραιος, οποιονδήποτε βασικό τύπο δεδομένων χρησιμοποιούμε.
Ο Παναγιώτης θα πει "ας δούμε τον μεγαλύτερο αριθμό που θα χρειαστούμε για να αποφασίσουμε πόσα bit χρειαζόμαστε". ΟΚ, ας πούμε ότι δεν γράφουμε τους πρώτους αριθμούς αλλά π.χ. τους αριθμούς από το 10000 και μετά, οπότε θα χρειαστούμε 5 ψηφία και στις δύο περιπτώσεις της εισόδου (είτε 10000 ως 10999 είτε 10000 ως 10099).
Δηλαδή η λέξη ή η ομάδα κελιών ή ο τύπος δεδομένων μας θα έχει αναγκαστικά πάντα 5 ψηφία. Νομίζω ότι κανείς μας δεν αναφέρεται σε τύπο δεδομένων με δυναμικά μεταβλητό αριθμό ψηφίων, σωστά;

Σ' αυτήν την περίπτωση η είσοδός μας δεν είναι στην πρώτη περίπτωση το 00999 και στην δεύτερη περίπτωση το 00099, άρα και στις δύο περιπτώσεις δεν θα έχουμε 5 ψηφία ως είσοδο;

edit: πιο απλός τρόπος να πω το ίδιο πράγμα:
Διάβασε α, β
Για ι από α μέχρι β
  Γράψε ι
Τέλος_επανάληψης

Το τρέχω δύο φορές: μία από 10000 ως 10999 και άλλη μία από 10000 ως 10099.
Εγώ λέω ότι και στις δύο εκτελέσεις, η είσοδός μου ήταν δύο αριθμοί, και η πολυπλοκότητα και στις δύο περιπτώσεις είναι Ο(Ν), όπου Ν=β-α
(δίνω δηλαδή ένα άλλο παράδειγμα αλγορίθμου όπου εγώ πιστεύω ότι η πολυπλοκότητα δεν μετριέται σε σχέση με το μέγεθος της εισόδου σε bit).
Εσείς σ' αυτό το παράδειγμα, πώς βγάζετε εκθετική την πολυπλοκότητα σε σχέση με την είσοδο;

[gpapargi]

Θέτω β-α=κ για λόγους ευκολίας. Το μέγεθος εισόδου είναι το πλήθος των ψηφίων. Το α έχει πλήθος ψηφίων log(α) και το β=α+κ έχει πλήθος ψηφίων log(α+κ). Άρα το μέγεθος εισόδου είναι log(α)+log(α+κ)=log[α*(α+κ)]=log(α^2+ακ). Το πλήθος των βημάτων είναι κ.
Άρα για τη συνάρτηση πολυπλοκότητας ισχύει f(log(α^2+ακ))=κ.
Για να βρω το f(ν) που είναι η συνάρτηση πολυπλοκότητας θα θέσω ν=log(α^2+ακ). Από αυτό προκύπτει ότι κ=(10^ν-α^2)/α. Άρα
f(ν)= (10^ν-α^2)/α που είναι εκθετική.

[gpapargi]

Για να συνεννοηθούμε καλύτερα, ίσως βοηθήσει η εξής παρατήρηση: άλλο είσοδος και άλλο το μέγεθος της εισόδου. πχ στον αριθμό 123 είσοδος είναι ο αριθμός 123 αλλά μέγεθος εισόδου είναι τα 3 ψηφία. Αλγόριθμοι εκθετικοί ως προς το μέγεθος εισόδου αλλά πολυωνυμικοί ως προς την αριθμητική τιμής της εισόδου λέγονται ψευδοπολυωνυμικοί και είναι εκθετικοί κατά βάση
https://en.wikipedia.org/wiki/Pseudo-polynomial_time

Η πολυπλοκότητα είναι συνάρτηση του μεγέθους εισόδου και όχι της αριθμητικής τιμής της εισόδου

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

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

[alkisg]

Γιώργο εγώ θέλω να υποστηρίξω αυτό:

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

Κι αυτό γιατί θεωρώ ότι κάποιοι συνάδελφοι έχουν στο νου τους ότι η πολυπλοκότητα εκφράζεται ΠΑΝΤΑ σε σχέση με το μέγεθος της εισόδου.

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

Έτσι θέτω ξανά προς συζήτηση ακριβώς τον ίδιο αλγόριθμο, αλλά με λίγο περισσότερη έμφαση σε ένα σημείο του:
"Να γραφεί αλγόριθμος που θα διαβάζει 2 αριθμούς με ακριβώς 5 ψηφία ο καθένας τους (δυαδικά, αν προτιμάς) και θα εμφανίζει όλα τα νούμερα που υπάρχουν μεταξύ τους. Τι πολυπλοκότητα έχει αυτός ο αλγόριθμος;"

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

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

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

[Diotima]

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

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

Διάβασε n
Για i από 1 μέχρι n
   Γράψε i
Τέλος_επανάληψης

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

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

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

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

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

Στο ερώτημα που θέτεις τώρα Άλκη για τους αριθμούς με σταθερά 5 ψηφία συμφωνώ μαζί σου, δε μπορεί να οριστεί εκφώνηση προβλήματος πολυπλοκότητας με τη λογική της εκφώνησης 2 που έγραψα παραπάνω, μόνο με τη λογική του 1, οπότε έχουμε Ο(n), όπου
n=β-α.

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

[gpapargi]

Γιώργο εγώ θέλω να υποστηρίξω αυτό:
Κι αυτό γιατί θεωρώ ότι κάποιοι συνάδελφοι έχουν στο νου τους ότι η πολυπλοκότητα εκφράζεται ΠΑΝΤΑ σε σχέση με το μέγεθος της εισόδου.

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

Έτσι θέτω ξανά προς συζήτηση ακριβώς τον ίδιο αλγόριθμο, αλλά με λίγο περισσότερη έμφαση σε ένα σημείο του:
"Να γραφεί αλγόριθμος που θα διαβάζει 2 αριθμούς με ακριβώς 5 ψηφία ο καθένας τους (δυαδικά, αν προτιμάς) και θα εμφανίζει όλα τα νούμερα που υπάρχουν μεταξύ τους. Τι πολυπλοκότητα έχει αυτός ο αλγόριθμος;"

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

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

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

Υπάρχει θεμελιώδες θέμα στο πρόβλημα που θέτεις. Δεν αφήνεις το μέγεθος εισόδου σου να πάει προς το άπειρο. Σε αυτή την περίπτωση δε λειτουργούν οι συμβολισμοί Ο() κλπ γιατί αναφέρονται στο πως συμπεριφέρονται οι συναρτήσεις όταν το μέγεθος εισόδου (ή ή όποια μεταβλητή) τείνει στο άπειρο. Συγκεκριμένα εκεί που λέει «για κάθε ν>ν0» υπάρχει πρόβλημα. Δεν αφήνεις το ν να ανέβει απεριόριστα κι έτσι μπορεί να δεις μια πολυωνυμική με κάποιο συντελεστή να είναι μεγαλύτερη από την εκθετική κλπ. Δηλαδή όταν φιξάρεις το μέγεθος εισόδου χάνει το πράγμα το νόημά του που είναι η συμπεριφορά στο άπειρο. Και χωρίς Ο() πώς να μιλήσεις για τάξη αλγορίθμου, αφού ο «μεγιστοβάθμιος» όρος μπορεί να μην δεν είναι μεγαλύτερος από κάποιον άλλο εντός των φραγμάτων μας.

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

[Diotima]

Έχεις απόλυτο δίκιο Γιώργο, διότι η διαφορά n=β-α για 5ψήφιους δε μπορεί να τείνει στο άπειρο, στη χειρότερη περίπτωση είναι σταθερή. Άρα η τάξη είναι Ο(1) και όχι Ο(n) άσχετα αν ο αλγόριθμος εκτελείται γραμμικά ως προς τη διαφορά.

[alkisg]

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

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

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

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

Αν θέλαμε να ζωγραφίσουμε την πολυπλοκότητα αυτού του προβλήματος, η γραφική παράσταση του χρόνου εκτέλεσης θα ήταν τριδιάστατη (και δυσνόητη) με βάση τις τιμές των α και β, διδιάστατη (και απλή γραμμή) με βάση την διαφορά α-β, και δεν μπορεί να ζωγραφιστεί με βάση τον αριθμό bits της εισόδου, γιατί δεν είναι συνάρτηση με βάση αυτά τα bit, αφού έχει πολλές τιμές y για το ίδιο x.

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

[alkisg]

Να πω και μια άλλη σκέψη σχετικά με το μέγεθος των τύπων δεδομένων, που ίσως διευκολύνει ακόμα περισσότερο το ξεκαθάρισμα του θέματος;

Στο παραπάνω παράδειγμα είχαμε δύο ακεραίους και προσπαθούσατε να συνδέσετε την πολυπλοκότητα με βάση το μέγεθος της εισόδου σε 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.

[gpapargi]

Θα απαντήσω σε ένα ένα τα θέματα  για να μην έχω πολύ μεγάλο μήνυμα.

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

Η ένσταση που έγραψα σε αυτό το σημείο είναι ουσιώδης, δεν ήταν απλά με σκοπό να παρακάμψω τη δυσκολία. Ισχύει ότι μπορούμε να μελετήσουμε μια συνάρτηση σε μια περιοχή φραγμένη, να πάρουμε δηλαδή ένα περιορισμό της. Δε λειτουργεί όμως η έννοια της τάξης. Να εξηγήσω διαισθητικά γιατί: Μπορείς να έχεις μια συνάρτηση f(n)=n κα μια g(n)=n^2/1000. Η g είναι Ο(n^2)  και η f είναι Ο(n). Όμως για μικρές του n  πχ κάτω από 1000 η f είναι μεγαλύτερη. Δηλαδή έχω μια τετραγωνική να είναι μικρότερη από μια γραμμική. Προφανώς όταν το n ανέβει προς το άπειρο η g θα ξεπεράσει την f με ότι αριθμό και να τη διαιρέσω αντί για το 1000 που διαιρώ εδώ. Αυτό είναι το νόημα το «για κάθε n>n0 θα ισχύει f(n)<g(n). Δηλαδή ναι μπορείς να βγάλεις το μεγιστοβάθμιο και να το αποκαλέσεις «τάξη» ή όπως αλλιώς θέλεις αλλά αυτό δεν έχει κάποια αξία. Πρέπει να αφήσεις το n να μεγαλώσει αρκετά για να «δείξει την αξία της» σε σχέση με το n^2/1000. Θέλεις υποχρεωτικά απειρισμό της ανεξάρτητης μεταβλητής αλλιώς, στις φραγμένες περιοχές,  η έννοια της τάξης δεν έχει την αξία που της αποδίδουμε. Θα δεις γραμμικές καλύτερες από εκθετικές κλπ.