ether συμφωνούμε σε όλα.
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των bits εισόδου, αλλά συναρτήσει κάποια άλλης μεταβλητής.
Κατά τη γνώμη μου επιτρέπεται όταν απλά πολλαπλασιάζεις την είσοδο με μια σταθερά πχ αντί για bits μετράς χαρακτήρες. Δεν πρόκειται αυτά να αλλάξει την τάξη του αλγορίθμου. Δεν επιτρέπεται όταν αλλάζεις την τάξη από πολυωνυμική σε εκθετική και ανάποδα. Το ερώτημα είναι: επιτρέπεται το να αλλάξεις από πολυωνυμική κάποιου βαθμού σε πολυωνυμική άλλου βαθμού (όπως κάνει το τετράδιο μαθητή στο παράδειγμα το ν σε ν^2); Ποια είναι τα όρια ανοχής;
Επίσης μια ερώτηση προς ether για να δούμε με ποια άποψη συμφωνείς ως προς την είσοδο: Ο παρακάτω αλγόριθμος έχει είσοδο;
Για ι από 1 ως 100
Γράψε ι
Τέλος_επανάληψης
Δηλαδή δεν έχω διάβασε. Έχει είσοδο ή όχι;
Στο CLRS (3rd edition, p. 25) αναφέρει:
The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study
Ο αλγόριθμος που έδωσες παραπάνω, αν κάθε φορά τον τρέχεις έτσι όπως είναι, χωρίς να αλλάξεις τις τιμές ΑΠΟ ΜΕΧΡΙ, έχει πολυπλοκότητα Ο(1) ως προς οποιαδήποτε είσοδο, γιατί οποιαδήποτε είσοδο κι αν του δώσεις την αγνοεί και εκτελεί πάντοτε τον συγκεκριμένο αριθμό εντολών.
Σχετικά με το παράδειγμα 2 του κεφ. 5 του τετραδίου μαθητή, προφανώς ως προς το πλήθος των στοιχείων του πίνακα (n^2) η πολυπλοκότητα του αλγορίθμου είναι γραμμική.
Αν υποθέσουμε όμως ότι ο πίνακας αυτός είναι ο πίνακας γειτνίασης ενός γράφου n κόμβων, τότε ενδεχομένως θα μας ενδιέφερε να μετρήσουμε την πολυπλοκότητα συναρτήσει του πλήθους των κόμβων n και να πούμε π.χ. ότι με το συγκεκριμένο τρόπο αναπαράστασης (πίνακας γειτνίασης), η πολυπλοκότητα εμφάνισης όλων των ακμών είναι O(n^2). Όπως λέει λοιπόν και το CLRS, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.