Θέμα: Ασκησούλα στην Πολυπλοκότητα

[gthal]

Γεια σας συνάδελφοι,
σκέφτομαι να βάλω αυτό το θεματάκι σε διαγώνισμα και θα ήθελα τις γνώμες σας.
Ευχαριστώ

[meteo_xampos]

Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (n=20) αφού ο ένας είναι γραμμικής και ο άλλος τετραγωνικής πολυπλοκότητας; Και γιατί να είναι 500 μs και όχι 20*10^-6 sec όπως μας λέει το βιβλίο στο πίνακα 5.3?

[apoldem]

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

(α) την πλήθος των "πράξεων" συναρτήσει του όγκου των δεδομένων n, π.χ. f(n)=5*n^2 + 2.5*n +105

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

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

[gthal]

Σας ευχαριστώ για τις απαντήσεις σας.
Βασικά αυτό που θέλω να εμπεδωθεί με αυτή την άσκηση είναι ότι στον γραμμικό αλγόριθμο θα χ-πλασιαστεί ο χρόνος αν χ-πλασιαστεί το μέγεθος, ενώ στον τετραγωνικό θα χ²-πλασιαστεί ο χρόνος αν χ-πλασιαστεί το μέγεθος.
Πώς πιστεύετε ότι θα μπορούσα να τη στήσω καλύτερα;
(μήπως αν πρόσθετα τη λέξη "περίπου" στους χρόνους; ή να έδινα μεγαλύτερα n; έτσι κι αλλιώς με παραξενεύει που το βιβλίο μας βάζει στο τριπάκι των μs, βασιζόμενο μάλιστα στην τόσο αφηρημένη και αυθαίρετη έννοια της "βασικής πράξης" στην οποία αποδίδει αυθαίρετα το 1μs - λίγο... μπακαλική μου μοιάζει όλο αυτό, αλλά νομίζω ότι και η άσκηση στέκεται επάξια στο πνεύμα του βιβλίου  )

Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (n=20) αφού ο ένας είναι γραμμικής και ο άλλος τετραγωνικής πολυπλοκότητας; Και γιατί να είναι 500 μs και όχι 20*10^-6 sec όπως μας λέει το βιβλίο στο πίνακα 5.3?

Επειδή λύνουν διαφορετικό πρόβλημα, μπορεί (από σύμπτωση) να κάνουν τον ίδιο χρόνο (απλά, ο τετραγωνικός λύνει ένα απλούστερο πρόβλημα, ας πούμε)
Όσο για τα μs, τι εννοείς; γιατί το χρησιμοποιώ ως μονάδα αντί του 10^-6 sec? Επειδή είναι το ίδιο, γράφεται πιο σύντομα και γενικά οι μαθητές τρομάζουν με τις μικρές δυνάμεις του 10.
Ή μήπως εννοείς ότι για n=20 θα έπρεπε να δίνει χρόνο 20 μs? γιατί δε νομίζω ότι το βιβλίο το υπολογίζει κάπως έτσι...   
Κατατόπισέ με περισσότερο αν θες...

[amavidis]

Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;

[itt]

Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (n=20) αφού ο ένας είναι γραμμικής και ο άλλος τετραγωνικής πολυπλοκότητας; Και γιατί να είναι 500 μs και όχι 20*10^-6 sec όπως μας λέει το βιβλίο στο πίνακα 5.3?

Πρακτικά γίνεται, γιατί ένας cache friendly O(n) αλγόριθμος μπορεί να έχει πολύ καλύτερη επίδοση (άρα και ακριβώς ίδια) με έναν O(logn) αλγόριθμο για τα ίδια δεδομένα. Έμφαση στο "πρακτικά", αφού στην ασυμπτωτική ανάλυση δεν μας απασχολούν οι σταθερές.

[meteo_xampos]

Στο σχήμα που προέρχεται από το βιβλίο, λέει ότι για γραμμική πολυπλοκότητα και n=20, ο χρόνος είναι 0.000002 sec, δηλαδή 20*10^-6 sec. Για τετραγωνική πολυπλοκότητα και n=20, 0.0004 sec, δηλαδή 20*20*10^-6 sec.

[gthal]

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

Δίκιο έχεις, δεν είχα προσέξει αυτή την... παραπλανητική σύμπτωση
Και τη λέω σύμπτωση γιατί με βάση τα όσα κατάλαβα από τη μελέτη του κεφαλαίου, δεν απορρέει ότι κάθε γραμμικός αλγόριθμος, για n στοιχεία θα κάνει n μs. Αλίμονο! Τότε θα ξέραμε εκ των προτέρων πόσο χρόνο θα κάνει ο οποιοσδήποτε γραμμικός αλγόριθμος ανεξάρτητα από το πλήθος των πράξεων που περιέχονται στους βρόχους του: 30 στοιχεία -> 30 μs , 100000 στοιχεία -> 100000 μs , όποιος κι αν είναι ο αλγόριθμος, απλά και μόνο επειδή είναι γραμμικός... Δεν πάει έτσι! Αντίθετα, νομίζω πως ένας γραμμικός αλγόριθμος για είκοσι στοιχεία  μπορεί να κάνει 20μs, όπως  μπορεί επίσης να κάνει... 78μs ή και 8466376μs - εξαρτάται από το τι επεξεργασία κάνει σε αυτά τα 20 στοιχεία.
Ούτε φυσικά αναμένω ότι κάθε τετραγωνικός θα κάνει n² μs.

Αυτά που έχω κακταλάβει είναι τα εξής
για έναν γραμμικό αλγόριθμο:
Αν για 20 στοιχεία κάνει 20μs τότε για 40 στοιχεία (τα διπλάσια), θα κάνει 40μs (τα διπλάσια επίσης)
όπως επίσης και
Αν για 20 στοιχεία κάνει... πες ... 73μs τότε για 40 στοιχεία (τα διπλάσια), θα κάνει 146μs (τα διπλάσια επίσης)
δηλ γενικά, αν για n στοιχεία κάνει t χρόνο, για k*n στοιχεία θα κάνει k*t χρόνο
ενώ για έναν τετραγωνικό:
Αν για 20 στοιχεία κάνει 20μs τότε για 40 στοιχεία (τα διπλάσια), θα κάνει 80μs (τα τετραπλάσια)
όπως επίσης και
Αν για 20 (ή για n) στοιχεία κάνει 73μs (ή t μs) τότε για 60 στοιχεία (ή k*20), θα κάνει k²*t  μs

Γιαυτό λέω ότι είναι παραπλανητικό το παράδειγμα, γιατί ενώ οι σχέσεις που φαίνονται οριζοντίως μέσα στις γραμμές του πράγαμτι ισχύουν,
οι σχέσεις που φαίνονται κατακορύφως στην στήλη n=20 δεν ισχύουν κατ' ανάγκη και μάλιστα οι τιμές είναι τέτοιες που οδηγούν κάποιον να πιστεύει ότι αν ο γραμμικός κάνει χ χρόνο, ο τετραγωνικός θα κάνει χ² και ο κυβικός χ³

Δεν ξέρω, αυτά έχω καταλάβει εγώ κι αν είμαι μακριά νυχτωμένος ξυπνήστε με το συνομότερο   

[tsak]

Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;

Αυτο αναρωτιέμαι κι εγω..

[gthal]

Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;

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