Ασυμπτωτικό πάνω και κάτω φράγμα

Απάντηση

Πρώτη μη αναγνωσμένη δημοσίευση • 1 δημοσίευση • Σελίδα 1 από 1

Mathletic: Δημοσιεύσεις: 275; Εγγραφή: Πέμ Μαρ 21, 2013 11:25 pm

Ασυμπτωτικό πάνω και κάτω φράγμα

Παράθεση

Μη αναγνωσμένη δημοσίευση από Mathletic » Τετ Μαρ 04, 2015 1:39 am

Γειά

Θέλω να βρω ασυμπτωτικό πάνω και κάτω φράγμα για το $T(n)=7T \left( \frac{n}{3} \right)+n^2$ .

Προσπάθησα τα εξής:

$a=7 \geq 1, b=3>1, f(n)=n^2$

$n^{\log_b a}=n^{\log_3 7} \approx n^{1.77}$

Άρα $f(n)=n^2=\Omega(n^{\log_b a}+ \epsilon)$ , για $\epsilon=0.23>0$ .

$af\left( \frac{n}{b} \right)=7 \left( \frac{n}{3}\right)^2=\frac{7n^2}{9}= \frac{7}{9}n^2 \leq cf(n)$ για οποιοδήποτε $c \in \left[ \frac{7}{9},1\right)$ .

Συνεπώς από την Περίπτωση 3 του Κεντρικού Θεωρήματος έχουμε ότι $T(n)=\Theta(f(n))=\Theta(n^2)$ .

Συμφωνείτε με την ισότητα αυτή: $n^{\log_b a}=n^{\log_3 7} \approx n^{1.77}$ ή είναι προτιμότερο να γράψω $n^{\log_b a}=n^{\log_3 7}< n^2$ ;

Απάντηση

1 δημοσίευση • Σελίδα 1 από 1

Επιστροφή σε “Μαθηματική Λογική & Θεμέλια Μαθηματικών”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης