Απορία στο βιβλίο

Ξεκίνησε από vtsakan, 21 Μαρ 2016, 10:36:44 ΠΜ

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

vtsakan

Καλημέρα!

Καταρχήν εάν το θέμα που θα θίξω έχει ήδη συζητηθεί. Έχω διαβάσει τις συνομιλίες, αλλά....

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

Μπορεί κάποιος να το εξηγήσει;

Ευχαριστώ.
Βασίλης Τσακανίκας
Ηλεκτρολόγος Μηχανικός και Μηχανικός Υπολογιστών Ε.Μ.Π.

gpapargi

Θα γράψω κάτι στα γρήγορα χωρίς να κάνω πράξεις.
Αν η πολυπλοκότητα είναι α+β*2^ν τότε έχω Ο(2^ν) και με κατάλληλη επιλογή των σταθερών μπορώ να ταιριάξω στα δεδομένα των 2 πρώτων στηλών. Το θέμα είναι αν για τις συγκεκριμένες σταθερές μπορεί να ταιριάξει και η τρίτη στήλη (ν=60). Αν δεν ταιριάξει μπορεί να έχω πολυπλοκότητα α+β*ν+γ*2^ν και να το μαγειρέψω κατάλληλα για να δέσει. Η ιδέα δηλαδή είναι να χρησιμοποιήσω κάποιες σταθερές και να λύσω το σύστημα ώστε να δέσουν τα δεδομένα.

vtsakan

 Ευχαριστώ.  Ρώτησα κυρίως γιατί στις από πάνω γραμμές η σχέση ειναι προφανής,  και άρα έχουν χρησιμοποιηθει συντελεστές ίσοι με τη μονάδα.  Ωστόσο,  από ότι καταλαβαίνω,  αυτό δεν ίσχυει στην εν λόγω γραμμή.
Βασίλης Τσακανίκας
Ηλεκτρολόγος Μηχανικός και Μηχανικός Υπολογιστών Ε.Μ.Π.