Πώς προκύπτει η ισότητα;

Mathletic · #1

Γειά χαρά.

Θεωρούμε την αναδρομιή σχέση T(n)=T(n-1)+n

.
Θέλουμε να δείξουμε ότι $T(n)=\Theta(n^2)$ .

$T(n)=O(n^2) \Rightarrow T(n) \leq c_2 n^2$

$T(n)=T(n-1)+n \leq c_2(n-1)^2+n=c_2n^2-2c_2n+c_2+n \\ =c_2n^2-c_2(2n-1)+n \leq c_2n^2$

αν $c_2(2n-1)-n \geq 0 \Rightarrow c_2 \geq \frac{n}{2n-1} \Rightarrow c_2 \geq \frac{1}{2}$

Άρα

.

$T(n)=\Omega(n^2) \Rightarrow T(n) \geq c_2 n^2$

$T(n)=T(n-1)+n \leq c_1(n-1)^2+n=c_1n^2-2c_1n+c_1+n \\ =c_1n^2-c_1(2n-1)+n \leq c_1n^2$

αν $c_1(2n-1)-n \geq 0 \Rightarrow c_1 \geq \frac{n}{2n-1} \Rightarrow c_1 \geq \frac{1}{2}$

Άρα T(n)=O(n^2)

.

Τότε $T(n)=\Theta(n^2)$ .

Πώς όμως συμπεραίνουμε από τα παραπάνω ότι $T(n)=\frac{n(n-1)}{2}$ ;

#2

Mathletic έγραψε:
Πώς όμως συμπεραίνουμε από τα παραπάνω ότι $T(n)=\frac{n(n-1)}{2}$ ;

Το πρώτο μέρος αυτών που γράφεις είναι εκτός πραγματικότητας.

Το τελευταίο που ρωτάς δεν βγαίνει από "τα παραπάνω" αλλά είναι τετριμμένη άσκηση στην επαγωγή.
Μόνο που πρέπει να έχεις και αρχική τιμή του T(0)

γιατί αλλιώς δεν έχει καν νόημα ούτε το ερώτημα.

Σου έχουμε συστήσει πολλές φορές ΝΑ ΣΚΕΠΤΕΣΑΙ τις ερωτήσεις πριν τις αναρτήσεις στο φόρουμ. Αλλιώς θα έχουμε
'αενάως τα ίδια φαινόμενα. Πότε θα κατανοήσεις τι προσπαθούμε να σου πούμε;

Πώς προκύπτει η ισότητα;

Πώς προκύπτει η ισότητα;

Re: Πώς προκύπτει η ισότητα;

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