מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 288:
==דוגמה לשילוב מספר כללים==
נפשט את הביטוי
<math dir = "ltr">\displaystyle f(n) = \sum_{i = 1}^n[\Theta(1) + \Theta(i)]</math>.
ראשית, נשים לב ש
<math dir = "ltr">\displaystyle \Theta(1) + \Theta(i) = \Theta(i + 1)</math>
מ[[#אדיטיביות|כלל האדיטיביות]]. אבל
<math dir = "ltr">\displaystyle \Theta(i + 1) = \Theta(i)</math>,
מפני ששני הביטויים בתוך ה<math dir = "ltr">\displaystyle \Theta</math> הם פולינומים ב<math dir = "ltr">\displaystyle i</math> בעלי דרגה 1. לכן נקבל
<math dir = "ltr">\displaystyle f(n) = \sum_{i = 1}^n[\Theta(i)]</math>.
כעת נשתמש שוב באדיטיבות:
<math dir = "ltr">\displaystyle f(n) =</math><br>
<math dir = "ltr">\displaystyle \sum_{i = 1}^n[\Theta(i)]=</math><br>
<math dir = "ltr">\displaystyle \Theta(1) + \Theta(2) + \cdots + \Theta(n)=</math><br>
<math dir = "ltr">\displaystyle \Theta(1 + 2 + \cdots + n=</math><br>
<math dir = "ltr">\displaystyle \Theta\left(\sum_{i = 1}^n[i] \right)</math>
אבל
<math dir = "ltr">\displaystyle \sum_{i = 1}^n[i] = \frac{n(n + 1)}{2}</math>,
מפני שזה [[מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/מתמטיקה#טורים שימושיים|טור חשבוני]] פשוט. לכן נקבל
<math dir = "ltr">\displaystyle f(n) = \Theta \left( \frac{n(n + 1)}{2} \right)</math>.
כלומר, <math dir = "ltr">\displaystyle \Theta</math> של פולינום ב<math dir = "ltr">\displaystyle n</math> בעל דרגה 2. לסיכום, לכן, נקבל <math dir = "ltr">\displaystyle f(n) = \Theta(n^2)</math>.
==סיכום==
| |||