Επίδοση και Πολυπλοκότητα - Ερώτηση 2η

Ξεκίνησε από gthal, 12 Νοε 2015, 11:28:52 ΜΜ

« προηγούμενο - επόμενο »

gthal

Έστω πίνακας Α 100 ακεραίων και θέλουμε να εμφανίσουμε το άθροισμα των στοιχείων του ανά δεκάδα, δηλαδή
Α[1]+Α[2]+Α[3]+ ... +Α[9]+Α[10] = ?
Α[11]+Α[12]+Α[13]+ ... +Α[19]+Α[20] = ?
...
Α[91]+Α[92]+Α[93]+ ... +Α[99]+Α[100] = ?

Δίνονται δύο αλγόριθμοι που επιλύουν το παραπάνω πρόβλημα



Αλγόριθμος λύση_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

Θεωρώ ότι χοντρικά και οι δύο κάνουν το ίδιο πλήθος πράξεων (ο 1ος καθυστερεί για τον υπολογισμό του δείκτη, ο δεύτερος καθυστερεί για τον έλεγχο της συνθήκης της Αν)
Ισχύει ότι ο πρώτος είναι O(n2)  και ο δεύτερος O(n)  ?
και τότε τι σημαίνει αυτό για τον δεύτερο? ότι είναι καλύτερος?
Φιλικά,
Γιώργος Θαλασσινός

evry

Αν υποθέσουμε ότι τα δεδομένα είναι Μ = Ν2
τότε και οι δυο αλγόριθμοι έχουν πολυπλοκότητα στη χειρότερη περίπτωση
O(M) = O(N*N) = O(N2)

Γενικά πάντως νομίζω ότι δεν έχει νόημα αυτή η συζήτηση αφού
α) δεν ορίζεται επακριβώς τι εννοούμε πράξεις
β) αποκλείω να ρωτήσει κάποιος στις εξετάσεις το πλήθος των πράξεων ενός αλγορίθμου αφού δεν έχει νόημα το Τ(ν) αλλά η ασυμπτωτική συμπεριφορά του, δηλαδή το Ο.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

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

evry

Η γνώμη μου είναι πως αν δεν μπορεί να ζητηθεί η τάξη ενός αλγορίθμου δεν μπορεί να ζητηθεί τίποτα άλλο, πόσο μάλλον ο επακριβής υπολογισμός των πράξεων που γίνονται.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

apoldem

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

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

gthal

Ευχαριστώ για τις απαντήσεις σας!

Παράθεση από: apoldem στις 13 Νοε 2015, 07:07:35 ΜΜ
Ο πρώτος αλγόριθμος, σε καμιά περίπτωση δεν είναι Ο(n^2).
Διαισθητικά συμφωνώ μαζί σου apoldem, αφού υπάρχει ισοδύναμος γραμμικός αλγόριθμος, θα πρέπει κι αυτός να θεωρείται O(n).
Όμως κι ο evry παραπάνω με είχε πείσει ότι έχουν την ίδια πολυπλοκότητα n2 με την έννοια ότι:
σ' αυτό το στιγμιότυπο του προβλήματος έχουμε 10 δεκάδες, σ' ένα άλλο 100 εκατοντάδες και γενικά σε κάποιο άλλο Ν Ν-άδες
Άρα ο ένας αλγόριθμος θα το λύσει με 2 εμφωλευμένες δομές που θα κάνουν Ν επαναλήψεις η καθεμιά - άρα Ν*Ν
ενώ ο άλλος θα το λύσει γραμμικά με μία δομή που θα κάνει Μ επαναλήψεις, όπου Μ=Ν*Ν
Οπότε είναι και οι δύο Ο(Ν2)
Έτσι, δεν ξέρω με ποια εξήγηση να πάω....

Παράθεση από: apoldem στις 13 Νοε 2015, 07:07:35 ΜΜ
Δεν αρκεί να έχεις φωλιασμένους βρόγχους για να γίνει η πολυπλοκότητα τετραγωνική.
Σωστό μου ακούγεται και αναρωτιέμαι.... αλήθεια, τι αρκεί ??  (χάριν της θεωρητικής τεκμηρίωσης)

Ακόμα, αν καταλαβαίνω σωστά τη λογική που περιγράφεις και τη χρησιμοποιήσω παρακάτω, μπορώ να αποδείξω ότι η φυσαλίδα είναι Ο(Ν) !!!
Ας πάρω την "έκδοση" της φυσαλίδας που δίνει το τετράδιο του μαθητή στο παράδειγμα 3, σελ 49 (που είναι "λίγο χειρότερη" από τη γνωστή φυσαλίδα):


Για i από 1 μέχρι N-1
  Για j από 1 από N-1
    ...


      που γράφεται ισοδύναμα:     
Για k από 1 μέχρι (Ν-1)^2
  i ← (k-1) div (Ν-1) +1
  j ← (k-1) mod (Ν-1) +1
  ...

Άρα με βάση τα προηγούμενα, δεν αρκεί το ότι η φυσαλίδα γίνεται με φωλιασμένες επαναλήψεις. Αφού μπορεί να γίνει και γραμμικά, είναι Ο(Ν)
(αλλά, βέβαια με ένα Ν που είναι ... της τάξης Ν2   :laugh: )

Οπότε... πού καταλήγουμε ?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

Η πολυπλοκότητα υπολογίζεται συγκρίνοντας τον χρόνο εκτέλεσης του αλγόριθμου καθώς μεγαλώνει το μέγεθος των δεδομένων.

Ερ. Ο πρώτος αλγόριθμος, πως θα συμπεριφερθεί αν του δώσουμε τα διπλάσια δεδομένα (πίνακα 200 θέσεων);
Απ. Θα κάνει τον διπλάσιο χρόνο.

Συνεπώς η πολυπλοκότητα είναι γραμμική Ο(n).

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

pgrontas

Σε κάθε περίπτωση η πολυπλοκότητα είναι ευθέως ανάλογη του πλήθους των δεδομένων, δηλαδή γραμμική.
O evry και o apoldem λένε το ίδιο πράγμα και έχουν φυσικά δίκιο.

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

Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gthal

Παράθεση από: apoldem στις 14 Νοε 2015, 06:22:16 ΜΜ
Ερ. Ο πρώτος αλγόριθμος, πως θα συμπεριφερθεί αν του δώσουμε τα διπλάσια δεδομένα (πίνακα 200 θέσεων);
Απ. Θα κάνει τον διπλάσιο χρόνο.
Α, αυτό το κάνει ξεκάθαρο! Ευχαριστώ!

Παράθεση από: pgrontas στις 14 Νοε 2015, 06:37:50 ΜΜ
Γιώργο, αυτό που σε μπερδεύει είναι ότι πας να υπολογίσεις την πολυπλοκότητα με βάση τον εμφωλευμένο βρόχο, ο οποίος όμως αφορά τις δεκάδες (ν-αδες) στις οποίες διαιρείς τα δεδομένα και όχι με βάση το μέγεθος της εισόδου
Κατάλαβα τι λες Παναγιώτη. Ευχαριστώ!
Φιλικά,
Γιώργος Θαλασσινός

gthal

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

Έστω 1600 στοιχεία που θέλω να επεξεργαστώ.
Μπορώ να τα αποθηκεύσω σαν μονοδιάστατο 1600 στοιχείων ή δισδιάτατο 40Χ40 ή 16Χ100 ή 160Χ10 κλπ κλπ κλπ
Και πάλι, ενώ τα στοιχεία είναι 1600, μπορώ να τα "διαιρέσω" σε 40-άδες, 100-άδες, 10-άδες κοκ
οπότε για την πολυπλοκότητα δεν θα έπρεπε να παίζει ρόλο αυτό αλλά το μέγεθος της εισόδου, το 1600
Στο παράδειγμα 2 όμως που αναφέρω κάνει το ίδιο πράγμα σε έναν πίνακα ΝΧΝ και καταλήγει ότι ο αλγόριθμος είναι τετραγωνικός!

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

Άρα η επεξεργασία δισδιάστατου πίνακα μου μοιάζει να μην είναι απαραίτητα Ν^2 έτσι?
Όμως η φυσαλίδα απαραίτητα είναι.
Ή το πρόβλημα της αναζήτησης κάθε στοιχείου ενός πίνακα Α, Ν στοιχείων σε έναν πίνακα Β, Μ στοιχείων? Μου φαίνεται ότι τετραγωνικής πολ/κότητας - δεν ξέρω γιατί... εδώ ποιο είναι το μέγεθος? Ν ή Μ? ή και τα δύο ? ή ΝΧΜ ? και αν 2πλασιάσω το μέγεθος, πώς αυξάνει η πολυπλοκότητα?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

Παρά το ότι απευθύνεσαι στον Παναγιώτη, πήρα το θάρος να επέμβω. Κατέβασα και διάβασα το παράδειγμα 2 του Βιβλίου Μαθητή και έφριξα! Τώρα καταλαβαίνω γιατί προσθέτεις όλες τις πράξεις. Υπάρχουν τέτοια παραδείγματα στο βιβλίο. Δύο παραδείγματα διάβασα και μου πέσαν τα μαλλιά. Από το παράδειγμα 2, αυτολεξή:

"Να υπολογισθεί ο χρόνος εκτέλεσης του αλγορίθμου αυτού και να σχολιασθεί η βαρύτητα των
πράξεων επανάληψης σε σχέση με την απόφαση για την πολυπλοκότητα των αλγορίθμων."

Πως μπορεί να υπολογιστεί ο "χρόνος εκτέλεσης"; Ποια είναι η "βαρύτητα των πράξεων"; Τι σημαίνει "απόφαση για την πολυπλοκότητα";

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

Το μέγεθος του πίνακα είναι το πλήθος των στοιχείων του (άλλο είναι οι διαστάσεις του πίνακα). Η πολυπλοκότητα ενδιαφέρεται για ΜΕΓΕΘΟΣ, όχι τις διαστάσεις. Αν θέλω να εκτυπώσω όλα τα στοιχεία ενός πίνακα και τα πάρω με την σειρά και τα τυπώσω, τότε έχω γραμμική πολυπλοκότητα. Για έναν διπλάσιο πίνακα, θα κάνω διπλάσιο χρόνο. Οι διαστάσεις των πινάκων μπορεί να είναι 2, 3, 7..., αλλά αυτό δεν με ενδιαφέρει. Οι διαστάσεις του πίνακα δεν αυξάνουν τον όγκο των δεδομένων (τα megabyte)

Διπλάσιο πίνακας είναι αυτός που έχει διπλάσια δεδομένα. Όπως ένα διπλάσιο σπίτι έχει διπλάσια τετραγωνικά μέτρα και ένα διπλάσιο χωράφι έχει τα διπλάσια στρέματα.

pgrontas

Κατ'αρχή συμφωνώ με τον apoldem ότι το παράδειγμα 2 σελ. 46 (νομίζω ή έχει αλλάξει η σελιδοποίηση;) είναι για τα μπάζα - και με τα υπόλοιπα. Απλά τα ξαναγράφω με δικά μου λόγια.   ;)

Το n που χρησιμοποιει συμβολίζει το πλήθος στοιχείων στη μία διάσταση του πίνακα. Στο παράδειγμα σου με τα 1600 δεδομένα το n είναι 40. Εννοεί λοιπόν ότι είναι τετραγωνικός ως προς αυτό.

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

Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

dpa2006

Πανελλαδικώς εξεταζόμενο το θέμα και η παράγραφος...
Λέτε να δούμε τέτοιο θέμα;
Στην αρχική έκδοση και παλαιότερες εκδόσεις του βιβλίου δεν το θυμάμαι... ???
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

apoldem

#13
Ξαναδιάβασα το παράδειγμα 2, της ενότητας 5.2, από το τετράδιο μαθητή (στο σπίτι αυτή την φορά, συντροφιά με φραπεδάκι).

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

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

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

Υ.Γ. Το συντακτικό και τα ρήματα που χρησιμοποιούνται στο κεφάλαιο αυτό σπάει κόκαλα. Από το παράδειγμα 3 αυτολεξή:

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

Δεν έχει σημασία ποιος είναι ο αλγόριθμος. Αυτό ζητείται από τον μαθητή! Χρειάζεται επιτροπή φιλολόγων για να κάνει συντακτική ανάλυση σ' αυτή την πρόταση. Να σκεφτεί κανείς ότι ο κεντρικός πυρήνας του μαθήματος είναι η σαφήνεια. Τόση σαφήνεια ώστε αυτό που λέμε να μπορεί να το καταλάβει μια μηχανή.

gthal

Παράθεση από: apoldem στις 16 Νοε 2015, 01:59:22 ΜΜ
Παρά το ότι απευθύνεσαι στον Παναγιώτη, πήρα το θάρος να επέμβω.
Καλά έκανες, εννοείται φίλε μου ! (μακάρι να ήξερα και το μικρό σου όνομα, να μη σε λέω με το username σου...)
και σ' ευχαριστώ για το χρόνο που διέθεσες  :)

Παράθεση από: apoldem στις 16 Νοε 2015, 08:11:33 ΜΜ
Το συντακτικό και τα ρήματα που χρησιμοποιούνται στο κεφάλαιο αυτό σπάει κόκαλα.
Πράγματι, και οι δύο εκφωνήσεις που παραθέτεις είναι τραγικές
Φιλικά,
Γιώργος Θαλασσινός

gthal

Παράθεση από: pgrontas στις 16 Νοε 2015, 02:51:36 ΜΜ
Το n που χρησιμοποιει συμβολίζει το πλήθος στοιχείων στη μία διάσταση του πίνακα. Στο παράδειγμα σου με τα 1600 δεδομένα το n είναι 40. Εννοεί λοιπόν ότι είναι τετραγωνικός ως προς αυτό.
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

Παράθεση
Παράθεση από: gthal στις 17 Νοε 2015, 08:55:55 ΠΜ
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

Το μέγεθος της εισόδου μπορεί να περιγράφεται από δύο ή περισσότερες παραμέτρους. Αν ακολουθήσουμε το σκεπτικό του παραδείγματος 2 και το εφαρμόσουμε σε πίνακα ΝΧΜ, τότε το μέγεθος της εισόδου είναι οι αριθμοί Ν και Μ και η πολυπλοκότητα προκύπτει ΝΧΜ.

gthal

Μα πώς θα ήταν η πολυπλοκότητα ΝΧΜ, αφού δεν υπάρχει τέτοιος συμβολισμός? Μπορούμε να πούμε ότι είναι Ο(ΝΧΜ) ? ? ?
Φιλικά,
Γιώργος Θαλασσινός

apoldem

Και βέβαια μπορούμε. Το μέγεθος της εισόδου μπορεί να περιγραφεί από περισσότερες μεταβλητές, ανεξάρτητες μεταξύ τους. Για παράδειγμα στα δίκτυα (ή γράφοι) είναι πολύ συνηθισμένο να μετράμε το μέγεθος τους με το πλήθος των κόμβων (n) και το πλήθος των συνδέσεων (m). Π.χ. ο διάσημος αλγόριθμος Dijkstra για τις συντομότερες διαδρομές έχει (χοντρικά) πολυπλοκότητα Ο(n+m).

Πιο γήινο παραδείγματα: Έχουμε δύο πίνακες ακεραίων Α[N] και Β[M]. Θέλουμε να βρούμε όλα τα ζευγάρια στοιχείων, που το ένα στοιχείο να ανήκει στον Α και το άλλο στον Β, και το άθροισμά τους να είναι 100.
Θα πρέπει να τσεκάρουμε όλα τα ζευγάρια στοιχείων μεταξύ Α και Β. Πολυπλοκότητα Ο(N*M).

Άλλο παράδειγμα: Έχουμε πάλι τους πίνακες Α[Ν] και Β[Μ]. Θέλουμε να βρούμε αν υπάρχει περίπτωση επιλέγοντας ένα οποιοδήποτε στοιχείο του Α και δύο οποιαδήποτε στοιχεία του Β να βρούμε άθροισμα 100. Εδώ τώρα επειδή διαλέγουμε 2 στοιχεία από το Β η πολυπλοκότητα θα βγει Ο(Ν*Μ2).

pgrontas

Παράθεση από: gthal στις 17 Νοε 2015, 08:55:55 ΠΜ
Ναι, το n στην προκειμένη τον βολεύει γιατί ο πίνακας είναι τετραγωνικός.
Αν ο πίνακας ήταν ΝΧΜ τι θα χρησιμοποιούσε σαν μέγεθος εισόδου ? ? ?

Μια παρατήρηση που ίσως διευκολύνει, ίσως και αναψει φωτιες.
Το n δεν είναι η είσοδος του αλγορίθμου.
Τα στοιχεία του πίνακα είναι η είσοδος.

Το n απλά ειναι κατι που πρέπει να έχει οριστεί πριν τρέξει ο αλγόριθμος.

Δηλ. δεν σημαίνει ότι οτιδήποτε υπάρχει στα δεδομένα θα επηρεάσει την πολυπλοκότητα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

itt

Παράθεση από: pgrontas στις 17 Νοε 2015, 08:16:24 ΜΜ
Μια παρατήρηση που ίσως διευκολύνει, ίσως και αναψει φωτιες.
Το n δεν είναι η είσοδος του αλγορίθμου.
Τα στοιχεία του πίνακα είναι η είσοδος.

Το n απλά ειναι κατι που πρέπει να έχει οριστεί πριν τρέξει ο αλγόριθμος.

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

Δεν καταλαβαίνω τι εννοείς. Η πολυπλοκότητα περιγράφει πώς αντιδρά ο αλγόριθμος (χωρικά|χρονικά) σε αλλαγές στο μέγεθος του input. Τι φωτιά ανάβει το ότι δεν έχει σχέση με τα δεδομένα per se;

gpapargi

Κατά η δική μου κατανόηση, η πολυπλοκότητα είναι μια συνάρτηση και θα πρέπει να ξεκαθαρίσεις ποια είναι ανεξάρτητη μεταβλητή σου. Δηλαδή να αποφασίσεις η πολυπλοκότητα συνάρτηση ποιου πράγματος είναι.
Τυπικά (δηλαδή με βάση τον ορισμό των μηχανώνΤuring) η πολυπλοκότητα είναι με βάση το χαρακτήρων που δίνεις να είσοδο. Γι αυτό θα δεις ότι ο έλεγχος για το αν ένας αριθμός είναι πρώτος, υπολογίζεται όχι με βάση τον αριθμό που ελέγχουμε αν είναι πρώτος, αλλά με βάση το πλήθος των ψηφίων του αριθμού. Πχ το επίτευγμα το αλγορίθμου AKS είναι ότι έλυσε το πρόβλημα σε πολυωνυμικό χρόνο από εκθετικός που ήταν πριν. Αν μετράγαμε με βάση τον αριθμό που ελέγχουμε (και όχι το πλήθος των ψηφίων του) θα ήταν εξαρχής πολυωνυμική η λύση.
Στην πράξη όμως το να πας τυπικά με το πλήθος των χαρακτήρων εισόδου είναι άβολο και πάμε με κάτι πιο βολικό/πρακτικό. Ότι μεταβλητή όμως και να χρησιμοποιήσουμε, μπορούμε να πάμε και σε άλλη μέσω σύνθεσης συναρτήσεων.
Πχ στον αλγόριθμο του τετραδίου με τον νΧν δισδιάστατο πίνακα, αν έχω μεταβλητή το ν τότε ναι πάω για τετραγωνική πολυπλοκότητα  (του ν). Αν έχω το πλήθος των στοιχείων (ν^2=π) τότε έχω γραμμική συνάρτηση του π (πλήθος). Συμφωνώ ότι είναι άκομψο το να διαλέξεις σα μεταβλητή το ν και όχι το πλήθος των στοιχείων. Γι αυτό ανέφερα και το παράδειγμα με τους πρώτους πιο πριν, για να δείξω το ρόλο της μεταβλητής που επιλέγω. Τελικά πιστεύω ότι είναι μαθηματικό παιχνίδι επιλογής της ανεξάρτητης μεταβλητής και κατασκευής συνάρτησης πάνω σε αυτή. Καλό είναι να διαλέγουμε μεταβλητή που να ταιριάζει με τη διαίσθησή μας.

pgrontas

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

Στο συγκεκριμένο παράδειγμα λοιπόν η επεξεργασία αφορά τα εισαγόμενα στοιχεία τα οποία απλά δείχνουμε (άρα αυτό αφορά την πολυπλοκότητα και είναι γραμμική).

Το ν απλά πρέπει να είναι γνωστό πριν ξεκινήσει ο αλγόριθμος, γι'αυτό υπάρχει στα δεδομένα.

itt (έστω και με καθυστέρηση): Οι φωτιές αναφέρονταν στο να μην ξεκινήσει η συζήτηση περι των ασαφειων της εντολής δεδομένα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

gpapargi

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

Δηλαδή στο παράδειγμα του βιβλίου, αν το δούμε διαισθητικά/σημασιολογικά η λογική επιλογή είναι το ν^2 σαν ανεξάρτητη μεταβλητή. Αν το δούμε σαν παιχνίδι επιλογής μεταβλητής μπορείς (έστω και αν είναι άκομψο) να έχεις ανεξάρτητη μεταβλητή το ν. Το παράδειγμα των πρώτων είναι που ανακατεύει το πράγμα.

pgrontas

Μάλλον δεν το εξέφρασα καλά.
Και στις δύο περιπτώσεις (πρώτοι και παράδειγμα) μας απασχολεί το μέγεθος της εισόδου. Στους πρώτους είναι τo μέγεθος της αναπαράστασης του αριθμού σε bits, ενώ στο παράδειγμα το πλήθος των αριθμών. Από  τη μία προσθέτοντας ένα bit διπλασιάζεται η δουλειά, από την άλλη προσθέτοντας έναν αριθμό η δουλειά απλά αυξάνεται κατά ένα.
Απλά στο παράδειγμα πρέπει να ανακαλύψουμε ποια είναι η είσοδος από τον αλγόριθμο και όχι να πάρουμε στα τυφλά ότι λέει η εντολή δεδομένα (η οποία δεν έχει πάντα σχέση με την είσοδο για την πολυπλοκότητα). Αυτό εννοώ με το σημασιολογία.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

petrosp13

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

gpapargi

#26
Κατάλαβα τι λες Παναγιώτη και συμφωνώ για το Δεδομένα //ν//. Πχ στους αραιούς δίνει το ν και ο πίνακας έχει μέγεθος 3ν.
Νομίζω όπως ότι η συζήτηση μοιραία θα περιστραφεί και γύρω από την είσοδο. Πχ δες ένα παράδειγμα:
Να γραφτεί αλγόριθμος που θα διαβάζει έναν ακέραιο αριθμό και θα εκτυπώνει τους ακέραιους από το 1 μέχρι αυτόν.
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης

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

ether

#27
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

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

pgrontas

Παράθεση από: gpapargi στις 08 Δεκ 2015, 05:20:51 ΜΜ
Η συζήτηση για την ανεξάρτητη μεταβλητή συναρτήσει της οποίας βγάζουμε την πολυπλοκότητα μοιραία επαναφέρει και το "στοιχειωμένο" ζήτημα της εισόδου. 
Συμφωνούμε 100%
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

itt

Παράθεση από: ether στις 08 Δεκ 2015, 06:21:46 ΜΜ
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

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

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

gpapargi

#30
Παράθεση από: ether στις 08 Δεκ 2015, 06:21:46 ΜΜ
Δε νομίζω να υπάρχει κάποιος που να θεωρεί ότι ο παρακάτω αλγόριθμος έχει γραμμική πολυπλοκότητα. Αφού μετράμε την πολυπλοκότητα συναρτήσει του μεγέθους της εισόδου, και εδώ η είσοδος είναι ο αριθμός ν, και το μέγεθος του ν είναι το πλήθος των ψηφίων του, ως προς το πλήθος των ψηφίων του ν ο συγκεκριμένος αλγόριθμος έχει εκθετική πολυπλοκότητα. Δε νομίζω να διαφωνεί κάποιος, αφού είναι γνωστό το θέμα τέτοιων αλγορίθμων (όπως ο brute force για τον έλεγχο πρώτου, ο αλγόριθμος δυναμικού προγραμματισμού για το knapsack), που τους χαρακτηρίζουν ψευδοπολυωνυμικούς γιατί είναι πολυωνυμικοί ως προς την αριθμητική τιμή της εισόδου, άρα είναι εκθετικοί ως προς το μέγεθος της εισόδου.

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


ether συμφωνούμε σε όλα.
Το ερώτημα για μένα που πρέπει να συζητήσουμε είναι το πότε επιτρέπεται να κάνουμε αλλαγή ανεξάρτητης μεταβλητής και να μην βρίσκουμε την πολυπλοκότητα συναρτήσει των bits εισόδου, αλλά συναρτήσει κάποια άλλης μεταβλητής.
Κατά τη γνώμη μου επιτρέπεται  όταν απλά πολλαπλασιάζεις την είσοδο με μια σταθερά πχ αντί για bits μετράς χαρακτήρες. Δεν πρόκειται αυτά να αλλάξει την τάξη του αλγορίθμου. Δεν επιτρέπεται όταν αλλάζεις την τάξη από πολυωνυμική σε εκθετική και ανάποδα. Το ερώτημα είναι: επιτρέπεται το να αλλάξεις από πολυωνυμική κάποιου βαθμού σε πολυωνυμική άλλου βαθμού (όπως κάνει το τετράδιο μαθητή στο παράδειγμα το ν σε ν^2); Ποια είναι τα όρια ανοχής;

Επίσης μια ερώτηση προς ether για να δούμε με ποια άποψη συμφωνείς ως προς την είσοδο: Ο παρακάτω αλγόριθμος έχει είσοδο;
Για ι από 1 ως 100
Γράψε ι
Τέλος_επανάληψης
Δηλαδή δεν έχω διάβασε. Έχει είσοδο ή όχι;

ether

#31
Παράθεση από: itt στις 09 Δεκ 2015, 11:38:10 ΠΜ
Οπότε λοιπόν εαν κάποιος κάνει την εύλογη ερώτηση με τον αλγόριθμο που έγραψες, τι του απαντάμε; Υπάρχει για μας η ψευδο-πολυωνυμική πολυπλοκότητα; Εγώ ειλικρινά δεν καταλαβαίνω γιατί αυτό το κεφαλαίο μπήκε στην ύλη.
Θα μπορούσαμε να δώσουμε διαφορετική απάντηση από αυτή που αναφέρεται στη σχετική βιβλιογραφία;
Όταν λες αν υπάρχει για εμάς η ψευδοπολυωνυμική πολυπλοκότητα, που ουσιαστικά είναι εκθετική ως προς το μέγεθος της εισόδου, τι εννοείς, στα πλαίσια της ΑΕΠΠ; Θεωρώ ότι είναι κάτι που δεν πρέπει να απασχολεί εμάς και τους μαθητές στα πλαίσια της ΑΕΠΠ και ούτε κι εγώ καταλαβαίνω γιατί μπήκε στην ύλη το συγκεκριμένο κεφάλαιο. Είναι κακογραμμένο, αλλά ακόμα και καλογραμμένο να ήταν θεωρώ ότι δε θα έπρεπε να αποτελεί αντικείμενο εξέτασης.

ether

Παράθεση από: gpapargi στις 09 Δεκ 2015, 02:58:03 ΜΜ
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, η έννοια του μεγέθους εισόδου εξαρτάται από το πρόβλημα και θα πρέπει να αναφέρεται.

gpapargi

Μια μικρή παρένθεση ως προς το αν έπρεπε να μπει ή όχι το κεφάλαιο 5 στην ύλη:
Πιο παλιά, έβλεπες εύρεση μεγίστου σε πίνακα με πλήρη ταξινόμηση. Σε κανέναν δεν άρεσε, αλλά κανείς δεν μπορούσε να κάνει τίποτα. Σου έλεγαν «μετράει μόνο το σωστό αποτέλεσμα» και «η πολυπλοκότητα είναι εκτός ύλης». Έπρεπε να βρεθεί ένα πλαίσιο για να μη δεχόμαστε σαν σωστούς εντελώς απαράδεκτους αλγορίθμους. Το κεφάλαιο 5 δίνει ένα τέτοιο πλαίσιο. Θα συζητήσουμε και θα ξεδιαλύνουμε τις λεπτομέρειες, δεν είναι η πρώτη φορά που γίνεται αυτό. Ίσα ίσα που το στέκι δείχνει να ξαναβρίσκει τον παλιό καλό του εαυτό που οι επιστημονικές  παιδαγωγικές συζητήσεις ήταν καθημερινότητα.   

gpapargi

Παράθεση από: ether στις 09 Δεκ 2015, 05:50:36 ΜΜ
Στο 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, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.

gpapargi

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

ether

#36
Παράθεση από: gpapargi στις 10 Δεκ 2015, 11:42:39 ΠΜ
Σύμφωνα με την άποψη που διατυπώνεις ether (διόρθωσέ με αν κατάλαβα λάθος) και πηγάζει από το CLR, το να δεις τον κώδικα (χωρίς εκφώνηση) στο παράδειγμα του τετραδίου μαθητή, δε σημαίνει τίποτα για την επιλογή της μεταβλητής ως προς την οποία θα υπολογίσουμε την πολυπλοκότητα. Τη μεταβλητή την επιλέγουμε με βάση τη φυσική σημασία του κώδικα και προέρχεται από την εκφώνηση. Έχουμε το δικαίωμα να επιλέξουμε ανεξάρτητη μεταβλητή και να φτιάξουμε τη συνάρτηση.
Γενικά δηλαδή ο κώδικας δεν καθορίζει τη μεταβλητή. Η εκφώνηση (=φυσική σημασία) την καθορίζει.
Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα δυο τετραγωνικών πινάκων ΝxN έχει τετραγωνική πολυπλοκότητα ως προς το Ν.
Ο αλγόριθμος της φυσσαλίδας για την ταξινόμηση ενός πίνακα Ν στοιχείων έχει επίσης τετραγωνική πολυπλοκότητα ως προς το Ν.
Και οι δύο έχουν διπλό εμφωλευμένο βρόχο (ίδιας τάξης πολυπλοκότητας).
Ο πρώτος έχει γραμμική πολυπλοκότητα ως προς το μέγεθος εισόδου και είναι βέλτιστος για το συγκεκριμένο πρόβλημα.
Ο δεύτερος έχει τετραγωνική πολυπλοκότητα ως προς το μέγεθος εισόδου και δεν είναι βέλτιστος για το συγκεκριμένο πρόβλημα.

Ο προφανής αλγόριθμος που υπολογίζει το άθροισμα των στοιχείων ενός πίνακα ΝxΜ έχει πολυπλοκότητα Ο(NM).
Ο κλασσικός αλγόριθμος δυναμικού προγραμματισμού για το 0/1 knapsack για N αντικείμενα με μέγιστο βάρος M έχει πολυπλοκότητα επίσης Ο(NM).
Και οι δύο έχουν διπλό εμφωλευμένο βρόχο (ίδιας τάξης πολυπλοκότητας).
Ο πρώτος έχει γραμμική πολυπλοκότητα ως προς το μέγεθος εισόδου και είναι βέλτιστος για το συγκεκριμένο πρόβλημα.
Ο δεύτερος έχει εκθετική πολυπλοκότητα ως προς το μέγεθος εισόδου (αν είχε γραμμική θα σήμαινε ότι P=NP οπότε θα ήμασταν (; ) όλοι χαρούμενοι) και δεν ξέρουμε αν είναι βέλτιστος για το συγκεκριμένο πρόβλημα (είναι πολύ πιθανό να είναι, παρόλο που ευχόμαστε (; ) να μην είναι)

ether

#37
Παράθεση από: gpapargi στις 10 Δεκ 2015, 01:18:09 ΜΜ
Γράφω ένα σχόλιο στην παραπάνω άποψη. Αν έχεις πίνακα γειτνίασης γράφου, η αύξηση των κόμβων κατά 1 σημαίνει  αύξηση των κελιών κατά 2ν+1=(ν+1)^2 - ν^2. Δε γίνεται να αυξήσεις τα κελιά του πίνακα κατά 1, αλλά μόνο κατά 2ν+1. Πάλι γραμμική είναι η πολυπλοκότητα ως προς το μέγεθος εισόδου. Το θέμα είναι αν μπορείς να ονομάσεις μέγεθος εισόδου το πλήθος των κόμβων τη στιγμή που κάθε νέος κόμβος σημαίνει αύξηση κατά μεταβλητό (2ν+1)πλήθος κελιών κάθε φορά. Αν θέλεις την πολυπλοκότητα συναρτήσει του ν φυσικά γίνεται.
Πάντως εγώ στο παραπάνω σχόλιό μου ανέφερα για το συγκεκριμένο θέμα ότι ενδεχομένως να μας ενδιέφερε ότι έχει τετραγωνική πολυπλοκότητα ως προς το πλήθος των κόμβων (αφού αν χρησιμοποιούσαμε ως αναπαράσταση του γραφήματος λίστες γειτνίασης ο αντίστοιχος αλγόριθμος θα είχε πολυπλοκότητα γραμμική ως προς το μέγεθος εισόδου, άρα μάλλον προτιμότερη σε σχέση με την τετραγωνική ως προς το πλήθος των κόμβων του αλγόριθμου με αναπαράσταση πίνακα γειτνίασης), δεν είπα κάτι για το μέγεθος εισόδου, ούτε και θεώρησα ως μέγεθος εισόδου το πλήθος των κόμβων.

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

gpapargi

Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;

ether

Παράθεση από: gpapargi στις 11 Δεκ 2015, 12:04:49 ΜΜ
Εντάξει συμφωνώ σε αυτά. Εμένα το πρόβλημα που με απασχολεί είναι το εξής:
Το μέγεθος της εισόδου τυπικά μετριέται στο πλήθος των bits εισόδου. Μπορώ επίσης να χρησιμοποιήσω κάποια άλλη μεταβλητή που να συνδέεται με το πλήθος των bits με κάποια πολλαπλασιαστική σταθερά πχ πλήθος χαρακτήρων. Το ερώτημα είναι: μπορώ να χρησιμοποιήσω κάποια άλλη μεταβλητή επειδή θέλω ή επειδή με βολεύει; Μπορώ πχ να πω ότι στον αλγόριθμο
Διάβασε ν
Για ι από 1 μέχρι ν
  Γράψε ι
Τέλος_επανάληψης
χρησιμοποιώ σαν μεταβλητή τον αριθμό εισόδου ν και έχω πολυπλοκότητα γραμμική ως προς ν ή είμαι παράτυπος;
Μπορώ πχ να εξηγήσω γιατί αν ταξινομώ πίνακες με αριθμούς χρησιμοποιώντας το πλήθος των αριθμών και όχι τα ψηφία τους έχω μεταβλητή πολλαπλασιασμένη με το πλήθος των bits εισόδου, αλλά τι γίνεται με το παράδειγμα που δίνω; Έχω δικαίωμα να εκφράσω πολυπλοκότητα ως προς ν αλλάζοντας την τάξη από εκθετική ως προς τα bits σε πολυωνυμική ως προς ν ή όχι;
Έχουμε λοιπόν έναν αλγόριθμο που δέχεται ως είσοδο έναν ακέραιο ν κι εμφανίζει όλους τους ακέραιους από το 1 μέχρι το ν.

Έχουμε κάθε δικαίωμα να πούμε ότι ο αλγόριθμός μας έχει πολυπλοκότητα Ο(ν). Δεν έχουμε όμως δικαίωμα να πούμε ότι ο αλγόριθμός μας είναι πολυωνυμικού χρόνου, αφού αυτό θα σήμαινε ότι είναι πολυωνυμικού χρόνου ως προς το μέγεθος της εισόδου (αφού ως προς το μέγεθος της εισόδου μετράμε την πολυπλοκότητα για να χαρακτηρίσουμε τον αλγόριθμο ως πολυωνυμικού, εκθετικού κτλ χρόνου), από τη στιγμή που το μέγεθος της εισόδου είναι lgν κι ο αλγόριθμός μας είναι Ο(2^lgν).

Και για τον αλγόριθμο δυναμικού προγραμματισμού για το knapsack, αναφέρουμε την πολυπλοκότητά του ως Ο(nW). Κανένας όμως αυτό δεν το ερμηνεύει ως πολυωνυμικού χρόνου, αφού στο συγκεκριμένο πρόβλημα το W δεν αντιστοιχεί σε πλήθος δεδομένων αλλά είναι απλά μια αριθμητική τιμή, άρα ουσιαστικά ο αλγόριθμος είναι εκθετικός, Ο(n*2^lgW), ως προς το μέγεθος της εισόδου.


gpapargi

Με βάση αυτά, στο παράδειγμα του τετραδίου μπορώ να πω ότι ο αλγόριθμος έχει τετραγωνική πολυπλοκότητα Ο(ν^2) αν και φυσικά δεν μπορώ να πω ότι είναι τετραγωνικός ως προς το χρόνος εκτέλεσης. Φοβάμαι πως θα δημιουργηθούν μπερδέματα.