Αποστολέας Θέμα: Απορία στο βιβλίο  (Αναγνώστηκε 539 φορές)

vtsakan

  • Ομάδα διαγωνισμάτων 2013
  • *
  • Μηνύματα: 273
  • printf("Smile");
Απορία στο βιβλίο
« στις: 21 Μάρ 2016, 10:36:44 πμ »
Καλημέρα!

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

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

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

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Απορία στο βιβλίο
« Απάντηση #1 στις: 21 Μάρ 2016, 03:27:53 μμ »
Θα γράψω κάτι στα γρήγορα χωρίς να κάνω πράξεις.
Αν η πολυπλοκότητα είναι α+β*2^ν τότε έχω Ο(2^ν) και με κατάλληλη επιλογή των σταθερών μπορώ να ταιριάξω στα δεδομένα των 2 πρώτων στηλών. Το θέμα είναι αν για τις συγκεκριμένες σταθερές μπορεί να ταιριάξει και η τρίτη στήλη (ν=60). Αν δεν ταιριάξει μπορεί να έχω πολυπλοκότητα α+β*ν+γ*2^ν και να το μαγειρέψω κατάλληλα για να δέσει. Η ιδέα δηλαδή είναι να χρησιμοποιήσω κάποιες σταθερές και να λύσω το σύστημα ώστε να δέσουν τα δεδομένα.

vtsakan

  • Ομάδα διαγωνισμάτων 2013
  • *
  • Μηνύματα: 273
  • printf("Smile");
Απ: Απορία στο βιβλίο
« Απάντηση #2 στις: 21 Μάρ 2016, 03:46:29 μμ »
 Ευχαριστώ.  Ρώτησα κυρίως γιατί στις από πάνω γραμμές η σχέση ειναι προφανής,  και άρα έχουν χρησιμοποιηθει συντελεστές ίσοι με τη μονάδα.  Ωστόσο,  από ότι καταλαβαίνω,  αυτό δεν ίσχυει στην εν λόγω γραμμή.
Βασίλης Τσακανίκας
Ηλεκτρολόγος Μηχανικός και Μηχανικός Υπολογιστών Ε.Μ.Π.