χμμμ...
ωραία, άρα το θέμα δεν είναι η μονάδα μέτρησης, αφού αλλού χρησιμοποιεί το δευτερόλεπτο, αλλού τη μέρα και αλλού τον αιώνα.
Οπότε το θέμα είναι πώς υπολογίζεται ο χρόνος. Αυτό εννοούσες, έτσι?
Δίκιο έχεις, δεν είχα προσέξει αυτή την... παραπλανητική
σύμπτωση Και τη λέω σύμπτωση γιατί με βάση τα όσα κατάλαβα από τη μελέτη του κεφαλαίου, δεν απορρέει ότι
κάθε γραμμικός αλγόριθμος, για n στοιχεία θα κάνει n μs. Αλίμονο! Τότε θα ξέραμε εκ των προτέρων πόσο χρόνο θα κάνει ο οποιοσδήποτε γραμμικός αλγόριθμος ανεξάρτητα από το πλήθος των πράξεων που περιέχονται στους βρόχους του: 30 στοιχεία -> 30 μs , 100000 στοιχεία -> 100000 μs , όποιος κι αν είναι ο αλγόριθμος, απλά και μόνο επειδή είναι γραμμικός... Δεν πάει έτσι! Αντίθετα, νομίζω πως ένας γραμμικός αλγόριθμος για είκοσι στοιχεία
μπορεί να κάνει 20μs, όπως
μπορεί επίσης να κάνει... 78μs ή και 8466376μs - εξαρτάται από το
τι επεξεργασία κάνει σε αυτά τα 20 στοιχεία.
Ούτε φυσικά αναμένω ότι
κάθε τετραγωνικός θα κάνει n
2 μ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
2*t μs
Γιαυτό λέω ότι είναι παραπλανητικό το παράδειγμα, γιατί ενώ οι σχέσεις που φαίνονται οριζοντίως μέσα στις γραμμές του πράγαμτι ισχύουν,
οι σχέσεις που φαίνονται κατακορύφως στην στήλη n=20 δεν ισχύουν κατ' ανάγκη και μάλιστα οι τιμές είναι τέτοιες που οδηγούν κάποιον να πιστεύει ότι αν ο γραμμικός κάνει χ χρόνο, ο τετραγωνικός θα κάνει χ
2 και ο κυβικός χ
3Δεν ξέρω, αυτά έχω καταλάβει εγώ κι αν είμαι μακριά νυχτωμένος ξυπνήστε με το συνομότερο
