| Αλγόριθμος λύση_1 Δεδομένα // A // Για i από 0 μέχρι 9 S <- 0 Για j από 1 μέχρι 10 S <- S +A[i*10+j] Τέλος_επανάληψης Εμφάνισε S Τέλος_επανάληψης Τέλος λύση_1 | Αλγόριθμος λύση_2 Δεδομένα // A // S <- 0 Για i από 1 μέχρι 100 S <- S + A[ i ] Αν i mod 10 = 0 τότε Εμφάνισε S S <- 0 Τέλος_αν Τέλος_επανάληψης Τέλος λύση_2 |
Ο πρώτος αλγόριθμος, σε καμιά περίπτωση δεν είναι Ο(n^2).Διαισθητικά συμφωνώ μαζί σου apoldem, αφού υπάρχει ισοδύναμος γραμμικός αλγόριθμος, θα πρέπει κι αυτός να θεωρείται O(n).
Δεν αρκεί να έχεις φωλιασμένους βρόγχους για να γίνει η πολυπλοκότητα τετραγωνική.Σωστό μου ακούγεται και αναρωτιέμαι.... αλήθεια, τι αρκεί ?? (χάριν της θεωρητικής τεκμηρίωσης)
| Για i από 1 μέχρι N-1 Για j από 1 από N-1 ... | που γράφεται ισοδύναμα: | Για k από 1 μέχρι (Ν-1)^2 i ← (k-1) div (Ν-1) +1 j ← (k-1) mod (Ν-1) +1 ... |
Ερ. Ο πρώτος αλγόριθμος, πως θα συμπεριφερθεί αν του δώσουμε τα διπλάσια δεδομένα (πίνακα 200 θέσεων);Α, αυτό το κάνει ξεκάθαρο! Ευχαριστώ!
Απ. Θα κάνει τον διπλάσιο χρόνο.
Γιώργο, αυτό που σε μπερδεύει είναι ότι πας να υπολογίσεις την πολυπλοκότητα με βάση τον εμφωλευμένο βρόχο, ο οποίος όμως αφορά τις δεκάδες (ν-αδες) στις οποίες διαιρείς τα δεδομένα και όχι με βάση το μέγεθος της εισόδουΚατάλαβα τι λες Παναγιώτη. Ευχαριστώ!
Παρά το ότι απευθύνεσαι στον Παναγιώτη, πήρα το θάρος να επέμβω.Καλά έκανες, εννοείται φίλε μου ! (μακάρι να ήξερα και το μικρό σου όνομα, να μη σε λέω με το username σου...)
Το συντακτικό και τα ρήματα που χρησιμοποιούνται στο κεφάλαιο αυτό σπάει κόκαλα.Πράγματι, και οι δύο εκφωνήσεις που παραθέτεις είναι τραγικές
Το n που χρησιμοποιει συμβολίζει το πλήθος στοιχείων στη μία διάσταση του πίνακα. Στο παράδειγμα σου με τα 1600 δεδομένα το n είναι 40. Εννοεί λοιπόν ότι είναι τετραγωνικός ως προς αυτό.Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?
Το μέγεθος της εισόδου μπορεί να περιγράφεται από δύο ή περισσότερες παραμέτρους. Αν ακολουθήσουμε το σκεπτικό του παραδείγματος 2 και το εφαρμόσουμε σε πίνακα ΝΧΜ, τότε το μέγεθος της εισόδου είναι οι αριθμοί Ν και Μ και η πολυπλοκότητα προκύπτει ΝΧΜ.
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?
Μια παρατήρηση που ίσως διευκολύνει, ίσως και αναψει φωτιες.
Το n δεν είναι η είσοδος του αλγορίθμου.
Τα στοιχεία του πίνακα είναι η είσοδος.
Το n απλά ειναι κατι που πρέπει να έχει οριστεί πριν τρέξει ο αλγόριθμος.
Δηλ. δεν σημαίνει ότι οτιδήποτε υπάρχει στα δεδομένα θα επηρεάσει την πολυπλοκότητα.
Η συζήτηση για την ανεξάρτητη μεταβλητή συναρτήσει της οποίας βγάζουμε την πολυπλοκότητα μοιραία επαναφέρει και το "στοιχειωμένο" ζήτημα της εισόδου.Συμφωνούμε 100%
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.
Διάβασε ν
Για ι από 1 μέχρι ν
Γράψε ι
Τέλος_επανάληψης
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.
Διάβασε ν
Για ι από 1 μέχρι ν
Γράψε ι
Τέλος_επανάληψης
Οπότε λοιπόν εαν κάποιος κάνει την εύλογη ερώτηση με τον αλγόριθμο που έγραψες, τι του απαντάμε; Υπάρχει για μας η ψευδο-πολυωνυμική πολυπλοκότητα; Εγώ ειλικρινά δεν καταλαβαίνω γιατί αυτό το κεφαλαίο μπήκε στην ύλη.Θα μπορούσαμε να δώσουμε διαφορετική απάντηση από αυτή που αναφέρεται στη σχετική βιβλιογραφία;
ether συμφωνούμε σε όλα.Στο CLRS (3rd edition, p. 25) αναφέρει:
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των 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, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.
Σύμφωνα με την άποψη που διατυπώνεις ether (διόρθωσέ με αν κατάλαβα λάθος) και πηγάζει από το CLR, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα δυο τετραγωνικών πινάκων ΝxN έχει τετραγωνική πολυπλοκότητα ως προς το Ν.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.
Γράφω ένα σχόλιο στην παραπάνω άποψη. Αν έχεις πίνακα γειτνίασης γράφου, η αύξηση των κόμβων κατά 1 σημαίνει αύξηση των κελιών κατά 2ν+1=(ν+1)^2 - ν^2. Δε γίνεται να αυξήσεις τα κελιά του πίνακα κατά 1, αλλά μόνο κατά 2ν+1. Πάλι γραμμική είναι η πολυπλοκότητα ως προς το μέγεθος εισόδου. Το θέμα είναι αν μπορείς να ονομάσεις μέγεθος εισόδου το πλήθος των κόμβων τη στιγμή που κάθε νέος κόμβος σημαίνει αύξηση κατά μεταβλητό (2ν+1)πλήθος κελιών κάθε φορά. Αν θέλεις την πολυπλοκότητα συναρτήσει του ν φυσικά γίνεται.Πάντως εγώ στο παραπάνω σχόλιό μου ανέφερα για το συγκεκριμένο θέμα ότι ενδεχομένως να μας ενδιέφερε ότι έχει τετραγωνική πολυπλοκότητα ως προς το πλήθος των κόμβων (αφού αν χρησιμοποιούσαμε ως αναπαράσταση του γραφήματος λίστες γειτνίασης ο αντίστοιχος αλγόριθμος θα είχε πολυπλοκότητα γραμμική ως προς το μέγεθος εισόδου, άρα μάλλον προτιμότερη σε σχέση με την τετραγωνική ως προς το πλήθος των κόμβων του αλγόριθμου με αναπαράσταση πίνακα γειτνίασης), δεν είπα κάτι για το μέγεθος εισόδου, ούτε και θεώρησα ως μέγεθος εισόδου το πλήθος των κόμβων.
Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:Έχουμε λοιπόν έναν αλγόριθμο που δέχεται ως είσοδο έναν ακέραιο ν κι εμφανίζει όλους τους ακέραιους από το 1 μέχρι το ν.
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;