Ασκησούλα στην Πολυπλοκότητα

Ξεκίνησε από gthal, 24 Φεβ 2016, 02:38:36 ΜΜ

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

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

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

Παράθεση από: meteo_xampos στις 24 Φεβ 2016, 11:36:52 ΜΜ
Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (n=20) αφού ο ένας είναι γραμμικής και ο άλλος τετραγωνικής πολυπλοκότητας; Και γιατί να είναι 500 μs και όχι 20*10-6 sec όπως μας λέει το βιβλίο στο πίνακα 5.3?
Επειδή λύνουν διαφορετικό πρόβλημα, μπορεί (από σύμπτωση) να κάνουν τον ίδιο χρόνο (απλά, ο τετραγωνικός λύνει ένα απλούστερο πρόβλημα, ας πούμε)
Όσο για τα μs, τι εννοείς; γιατί το χρησιμοποιώ ως μονάδα αντί του 10-6 sec? Επειδή είναι το ίδιο, γράφεται πιο σύντομα και γενικά οι μαθητές τρομάζουν με τις μικρές δυνάμεις του 10.
Ή μήπως εννοείς ότι για n=20 θα έπρεπε να δίνει χρόνο 20 μs? γιατί δε νομίζω ότι το βιβλίο το υπολογίζει κάπως έτσι...   :-\
Κατατόπισέ με περισσότερο αν θες...
Φιλικά,
Γιώργος Θαλασσινός

amavidis

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

itt

Παράθεση από: meteo_xampos στις 24 Φεβ 2016, 11:36:52 ΜΜ
Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (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 στοιχεία.
Ούτε φυσικά αναμένω ότι κάθε τετραγωνικός θα κάνει n2 μ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), θα κάνει k2*t  μs

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

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

tsak

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

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


gthal

Παράθεση από: amavidis στις 25 Φεβ 2016, 04:44:44 ΜΜ
Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;
Για μένα, η ερώτηση αυτή είναι συμπλήρωσης κενού και εξετάζει την κατανόηση αυτού που λέει στην τελευταία παράγραφο της σελ 106 - από την παλιά έκδοση (θα μπορούσε να στηθεί με πολλούς τρόπους και να εξετάζει το ίδιο πράγμα)
Οπότε, τη βλέπω ως ερώτηση θεωρίας.
Φιλικά,
Γιώργος Θαλασσινός