Το δέντρο της αναδρομής - 3 ασκήσεις για την ΠΛΗ 30
0 likes304 views
The document discusses solving recursive equations using recursion trees, presenting three exercises with detailed analyses and calculations for each equation. Key insights include determining upper and lower bounds for the solutions, establishing that t(n) = θ(n) for the given recursive equations. The author, Anna Korfiati, provides a structured approach for each problem, illustrated with mathematical formulas and contributions from different levels of the recursion tree.
Το δέντρο της αναδρομής - 3 ασκήσεις για την ΠΛΗ 30
- 1. – Άννα Κορφιάτη | korfiati.an@gmail.com | https://www.facebook.com/mathwithcoding | 6974 12 9730 Επίλυση αναδρομικών εξισώσεων Το δέντρο της αναδρομής Άσκηση 1 Να λυθεί η αναδρομική εξίσωση 𝑇(𝑛) = 𝑇 ( 𝑛 5 ) + 𝑇 ( 𝑛 10 ) + 𝑛 με την χρήση του δέντρου της αναδρομής Λύση Αρχικά θέτουμε 𝑘 το ύψος του δέντρου. Η λύση της αναδρομικής εξίσωσης προκύπτει αν αθροίσουμε τη συνεισφορά κάθε επιπέδου. Το ύψος του δέντρου θα προσδιοριστεί από τον αριθμό των μειώσεων στο μέγεθος του μεγαλύτερου υποπροβλήματος. Έχουμε λοιπόν 𝛵(𝑛) = ∑ ( 3 10 ) 𝑖 𝑛 𝑘 𝑖=0 Κάτω φράγμα Ισχύει 𝛵(𝑛) = ∑ ( 3 10 ) 𝑖 𝑛 𝑘 𝑖=0 = 𝑛 + ∑ ( 3 10 ) 𝑖 𝑛 𝑘 𝑖=1 ≥ 𝑛 Άρα 1 ⋅ 𝑛 ≤ 𝑇(𝑛) για 𝑛 ≥ 1 δηλαδή 𝜯(𝒏) = 𝜴(𝒏)
- 2. – Άννα Κορφιάτη | korfiati.an@gmail.com | https://www.facebook.com/mathwithcoding | 6974 12 9730 Άνω φράγμα Έχουμε ακόμη ∑ ( 3 10 ) 𝑖 𝑛 𝑘 𝑖=0 ≤ ∑ ( 3 10 ) 𝑖 𝑛 ∞ 𝑖=0 = 𝑛 ⋅ 1 1 − 3 10 = 𝑛 ⋅ 1 7 10 = 10 7 𝑛 Άρα 𝑇(𝑛) ≤ 10 7 𝑛 για 𝑛 ≥ 1 δηλαδή 𝜯(𝒏) = 𝑶(𝒏) Άρα 𝜯(𝒏) = 𝜣(𝒏)
- 3. – Άννα Κορφιάτη | korfiati.an@gmail.com | https://www.facebook.com/mathwithcoding | 6974 12 9730 Άσκηση 2 Να λυθεί η αναδρομική εξίσωση 𝑇(𝑛) = 𝑇 ( 𝑛 7 ) + 𝑇 ( 𝑛 49 ) + 𝑛με την χρήση του δέντρου της αναδρομής Λύση Σημείωση: Στο παρακάτω δέντρο, με μαύρο χρώμα σημειώνεται το μέγεθος των δεδομένων και με κόκκινο χρώμα ο χρόνος. Εδώ τυχαίνει να συμπίπτουν, επομένως το κόκκινο χρώμα στους κόμβους χρησιμοποιείται ενδεικτικά. Συμβολίζουμε ℎ το ύψος του δέντρου και έχουμε: 𝛵1(𝑛) = ∑ ( 8 49 ) 𝑖 𝑛 ℎ 𝑖=0 Κάτω φράγμα: 𝑛 ≤ ∑ ( 8 49 ) 𝑖 𝑛 ℎ 𝑖=0
- 4. – Άννα Κορφιάτη | korfiati.an@gmail.com | https://www.facebook.com/mathwithcoding | 6974 12 9730 Άνω φράγμα: ∑ ( 8 49 ) 𝑖 𝑛 ℎ 𝑖=0 ≤ ∑ ( 8 49 ) 𝑖 𝑛 ∞ 𝑖=0 = 1 1 − 8 49 𝑛 = 1 41 49 𝑛 = 49 41 𝑛 Άρα 𝑛 ≤ ∑ ( 8 49 ) 𝑖 𝑛 ℎ 𝑖=0 ≤ 49 41 𝑛 Επομένως 𝜯(𝒏) = 𝜣(𝒏)
- 5. – Άννα Κορφιάτη | korfiati.an@gmail.com | https://www.facebook.com/mathwithcoding | 6974 12 9730 Άσκηση 3 Να λυθεί η αναδρομική εξίσωση 𝑇(𝑛) = 𝑇 ( 𝑛 3 ) + 𝑇 ( 𝑛 6 ) + 𝑇 ( 𝑛 9 ) + 𝑛 με την χρήση του δέντρου της αναδρομής Ανακαλύπτουμε το μοτίβο: Στο κόκκινο επίπεδο έχουμε: Στο πορτοκαλί επίπεδο έχουμε: Άρα είναι:
- 6. – Άννα Κορφιάτη | korfiati.an@gmail.com | https://www.facebook.com/mathwithcoding | 6974 12 9730 Αρχικά θέτουμε 𝑘 το ύψος του δέντρου. Η λύση της αναδρομικής εξίσωσης προκύπτει αν αθροίσουμε τη συνεισφορά κάθε επιπέδου. Το ύψος του δέντρου θα προσδιοριστεί από τον αριθμό των μειώσεων στο μέγεθος του μεγαλύτερου υποπροβλήματος. Έχουμε λοιπόν 𝛵(𝑛) = ∑ ( 11 18 ) 𝑖 𝑛 𝑘 𝑖=0 Κάτω φράγμα Ισχύει 𝛵(𝑛) = ∑ ( 11 18 ) 𝑖 𝑛 𝑘 𝑖=0 = 𝑛 + ∑ ( 11 18 ) 𝑖 𝑛 𝑘 𝒊=𝟏 ≥ 𝑛 Άρα 1 ⋅ 𝑛 ≤ 𝑇(𝑛) για 𝑛 ≥ 1 δηλαδή 𝜯(𝒏) = 𝜴(𝒏) Άνω φράγμα Έχουμε ακόμη ∑ ( 11 18 ) 𝑖 𝑛 𝑘 𝑖=0 ≤ ∑ ( 11 18 ) 𝑖 𝑛 ∞ 𝑖=0 = 𝑛 ⋅ 1 1 − 11 18 = 𝑛 ⋅ 1 7 18 = 18 7 𝑛 Άρα 𝑇(𝑛) ≤ 18 7 𝑛 για 𝑛 ≥ 1 δηλαδή 𝜯(𝒏) = 𝑶(𝒏) Άρα 𝜯(𝒏) = 𝜣(𝒏)