Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Μήνυμα ξεκίνησε από: vtsakan στις 21 Μάρ 2016, 10:36:44 πμ

Τίτλος: Απορία στο βιβλίο
Αποστολή από: vtsakan στις 21 Μάρ 2016, 10:36:44 πμ
Καλημέρα!

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

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

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

Ευχαριστώ.
Τίτλος: Απ: Απορία στο βιβλίο
Αποστολή από: gpapargi στις 21 Μάρ 2016, 03:27:53 μμ
Θα γράψω κάτι στα γρήγορα χωρίς να κάνω πράξεις.
Αν η πολυπλοκότητα είναι α+β*2^ν τότε έχω Ο(2^ν) και με κατάλληλη επιλογή των σταθερών μπορώ να ταιριάξω στα δεδομένα των 2 πρώτων στηλών. Το θέμα είναι αν για τις συγκεκριμένες σταθερές μπορεί να ταιριάξει και η τρίτη στήλη (ν=60). Αν δεν ταιριάξει μπορεί να έχω πολυπλοκότητα α+β*ν+γ*2^ν και να το μαγειρέψω κατάλληλα για να δέσει. Η ιδέα δηλαδή είναι να χρησιμοποιήσω κάποιες σταθερές και να λύσω το σύστημα ώστε να δέσουν τα δεδομένα.
Τίτλος: Απ: Απορία στο βιβλίο
Αποστολή από: vtsakan στις 21 Μάρ 2016, 03:46:29 μμ
 Ευχαριστώ.  Ρώτησα κυρίως γιατί στις από πάνω γραμμές η σχέση ειναι προφανής,  και άρα έχουν χρησιμοποιηθει συντελεστές ίσοι με τη μονάδα.  Ωστόσο,  από ότι καταλαβαίνω,  αυτό δεν ίσχυει στην εν λόγω γραμμή.