Αποστολέας Θέμα: Ασκησούλα στην Πολυπλοκότητα  (Αναγνώστηκε 1740 φορές)

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 891
Ασκησούλα στην Πολυπλοκότητα
« στις: 24 Φεβ 2016, 02:38:36 μμ »
Γεια σας συνάδελφοι,
σκέφτομαι να βάλω αυτό το θεματάκι σε διαγώνισμα και θα ήθελα τις γνώμες σας.
Ευχαριστώ
Φιλικά,
Γιώργος Θαλασσινός

meteo_xampos

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 182
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #1 στις: 24 Φεβ 2016, 11:36:52 μμ »
Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (n=20) αφού ο ένας είναι γραμμικής και ο άλλος τετραγωνικής πολυπλοκότητας; Και γιατί να είναι 500 μs και όχι 20*10-6 sec όπως μας λέει το βιβλίο στο πίνακα 5.3?

apoldem

  • Βετεράνος
  • ****
  • Μηνύματα: 86
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #2 στις: 24 Φεβ 2016, 11:56:06 μμ »
Δεν μπορείς να υπολογίσεις τον χρόνο εκτέλεσης, γνωρίζοντας μόνο την πολυπλοκότητα. Για να υπολογίσεις ακριβώς τον χρόνο εκτέλεσης, πρέπει να ξέρεις δύο πράγματα:

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

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

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

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 891
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #3 στις: 25 Φεβ 2016, 09:17:20 πμ »
Σας ευχαριστώ για τις απαντήσεις σας.
Βασικά αυτό που θέλω να εμπεδωθεί με αυτή την άσκηση είναι ότι στον γραμμικό αλγόριθμο θα χ-πλασιαστεί ο χρόνος αν χ-πλασιαστεί το μέγεθος, ενώ στον τετραγωνικό θα χ2-πλασιαστεί ο χρόνος αν χ-πλασιαστεί το μέγεθος.
Πώς πιστεύετε ότι θα μπορούσα να τη στήσω καλύτερα;
(μήπως αν πρόσθετα τη λέξη "περίπου" στους χρόνους; ή να έδινα μεγαλύτερα n; έτσι κι αλλιώς με παραξενεύει που το βιβλίο μας βάζει στο τριπάκι των μs, βασιζόμενο μάλιστα στην τόσο αφηρημένη και αυθαίρετη έννοια της "βασικής πράξης" στην οποία αποδίδει αυθαίρετα το 1μs - λίγο... μπακαλική μου μοιάζει όλο αυτό, αλλά νομίζω ότι και η άσκηση στέκεται επάξια στο πνεύμα του βιβλίου  :P)

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

amavidis

  • ΠΛΗΝΕΤ
  • *
  • Μηνύματα: 76
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #4 στις: 25 Φεβ 2016, 04:44:44 μμ »
Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #5 στις: 25 Φεβ 2016, 04:45:29 μμ »
Πώς γίνεται οι δυο αλγόριθμοι να έχουν ίδιο χρόνο εκτέλεσης για τα ίδια δεδομένα (n=20) αφού ο ένας είναι γραμμικής και ο άλλος τετραγωνικής πολυπλοκότητας; Και γιατί να είναι 500 μs και όχι 20*10-6 sec όπως μας λέει το βιβλίο στο πίνακα 5.3?

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


meteo_xampos

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 182
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #6 στις: 25 Φεβ 2016, 10:31:43 μμ »
Στο σχήμα που προέρχεται από το βιβλίο, λέει ότι για γραμμική πολυπλοκότητα και n=20, ο χρόνος είναι 0.000002 sec, δηλαδή 20*10-6 sec. Για τετραγωνική πολυπλοκότητα και n=20, 0.0004 sec, δηλαδή 20*20*10-6 sec.

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 891
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #7 στις: 26 Φεβ 2016, 01:35:41 μμ »
χμμμ...
ωραία, άρα το θέμα δεν είναι η μονάδα μέτρησης, αφού αλλού χρησιμοποιεί το δευτερόλεπτο, αλλού τη μέρα και αλλού τον αιώνα.
Οπότε το θέμα είναι πώς υπολογίζεται ο χρόνος. Αυτό εννοούσες, έτσι?

Δίκιο έχεις, δεν είχα προσέξει αυτή την... παραπλανητική σύμπτωση
Και τη λέω σύμπτωση γιατί με βάση τα όσα κατάλαβα από τη μελέτη του κεφαλαίου, δεν απορρέει ότι κάθε γραμμικός αλγόριθμος, για 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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 130
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #8 στις: 26 Φεβ 2016, 11:06:37 μμ »
Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;

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


gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 891
Απ: Ασκησούλα στην Πολυπλοκότητα
« Απάντηση #9 στις: 27 Φεβ 2016, 09:02:08 μμ »
Συνάδελφοι, αφού η πολυπλοκότητα διδάσκεται θεωρητικά (βάση των οδηγιών Δεκ. 2015). Ποια η σκοπιμότητα της άσκησης;
Για μένα, η ερώτηση αυτή είναι συμπλήρωσης κενού και εξετάζει την κατανόηση αυτού που λέει στην τελευταία παράγραφο της σελ 106 - από την παλιά έκδοση (θα μπορούσε να στηθεί με πολλούς τρόπους και να εξετάζει το ίδιο πράγμα)
Οπότε, τη βλέπω ως ερώτηση θεωρίας.
Φιλικά,
Γιώργος Θαλασσινός