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

[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(n²)  και ο δεύτερος O(n)  ?
και τότε τι σημαίνει αυτό για τον δεύτερο? ότι είναι καλύτερος?

[evry]

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

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

[petrosp13]

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

[evry]

Η γνώμη μου είναι πως αν δεν μπορεί να ζητηθεί η τάξη ενός αλγορίθμου δεν μπορεί να ζητηθεί τίποτα άλλο, πόσο μάλλον ο επακριβής υπολογισμός των πράξεων που γίνονται.

[apoldem]

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

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

[gthal]

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

Ο πρώτος αλγόριθμος, σε καμιά περίπτωση δεν είναι Ο(n^2).

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

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

Σωστό μου ακούγεται και αναρωτιέμαι.... αλήθεια, τι αρκεί ??  (χάριν της θεωρητικής τεκμηρίωσης)

Ακόμα, αν καταλαβαίνω σωστά τη λογική που περιγράφεις και τη χρησιμοποιήσω παρακάτω, μπορώ να αποδείξω ότι η φυσαλίδα είναι Ο(Ν) !!!
Ας πάρω την "έκδοση" της φυσαλίδας που δίνει το τετράδιο του μαθητή στο παράδειγμα 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   ...

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

Οπότε... πού καταλήγουμε ?

[apoldem]

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

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

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

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

[pgrontas]

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

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

[gthal]

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

Α, αυτό το κάνει ξεκάθαρο! Ευχαριστώ!

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

Κατάλαβα τι λες Παναγιώτη. Ευχαριστώ!

[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. Εννοεί λοιπόν ότι είναι τετραγωνικός ως προς αυτό.

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

[dpa2006]

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

[apoldem]

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

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

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

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

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

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

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

[gthal]

Παρά το ότι απευθύνεσαι στον Παναγιώτη, πήρα το θάρος να επέμβω.

Καλά έκανες, εννοείται φίλε μου ! (μακάρι να ήξερα και το μικρό σου όνομα, να μη σε λέω με το username σου...)
και σ' ευχαριστώ για το χρόνο που διέθεσες 

Το συντακτικό και τα ρήματα που χρησιμοποιούνται στο κεφάλαιο αυτό σπάει κόκαλα.

Πράγματι, και οι δύο εκφωνήσεις που παραθέτεις είναι τραγικές