נוסחת נסיגה עם שורש[ עריכה ]
בנוסחת הנסיגה
T
(
n
)
=
T
(
n
)
+
log
(
n
)
{\displaystyle \displaystyle T(n)=T({\sqrt {n}})+\log(n)}
,
T
(
n
)
{\displaystyle \displaystyle T(n)}
מתארת את זמן הריצה של אלגוריתם כלשהו. אנא פתור את הנוסחה.
נשתמש בפרישה .בעץ המתאים לנוסחה:
צומת הראש מציין את
T
(
n
)
{\displaystyle \displaystyle T(n)}
, והרמה הראשונה תורמת
log
(
n
)
{\displaystyle \displaystyle \log(n)}
.
ברמה הבאה, הצומת מציין את
T
(
n
)
=
t
(
n
1
/
2
)
{\displaystyle \displaystyle T({\sqrt {n}})=t(n^{1/2})}
, והרמה תורמת
log
(
n
)
=
1
/
2
⋅
log
(
n
)
{\displaystyle \displaystyle \log({\sqrt {n}})=1/2\cdot \log(n)}
.
ברמה הבאה אחריה, הצומת מציין את
T
(
n
1
/
2
)
=
t
(
n
1
/
4
)
{\displaystyle \displaystyle T({\sqrt {n^{1/2}}})=t(n^{1/4})}
, והרמה תורמת
log
(
n
1
/
2
)
=
1
/
4
⋅
log
(
n
)
{\displaystyle \displaystyle \log({\sqrt {n^{1/2}}})=1/4\cdot \log(n)}
.
החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה
i
{\displaystyle \displaystyle i}
(כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את
T
(
n
1
/
2
i
)
{\displaystyle \displaystyle T(n^{1/2^{i}})}
, והרמה תורמת
1
/
2
i
⋅
log
(
n
)
{\displaystyle \displaystyle 1/2^{i}\cdot \log(n)}
.
כדי למצוא את גובה העץ,
m
{\displaystyle \displaystyle m}
, נפתור
n
1
/
2
i
=
2
{\displaystyle \displaystyle n^{1/2^{i}}=2}
:
n
1
/
2
m
=
2
{\displaystyle \displaystyle n^{1/2^{m}}=2}
log
(
n
1
/
2
m
)
=
1
{\displaystyle \displaystyle \log(n^{1/2^{m}})=1}
1
/
2
m
⋅
log
(
n
)
=
1
{\displaystyle \displaystyle 1/2^{m}\cdot \log(n)=1}
2
m
=
log
(
n
)
{\displaystyle \displaystyle 2^{m}=\log(n)}
m
=
log
(
log
(
n
)
)
{\displaystyle \displaystyle m=\log(\log(n))}
כאמור, הרמה ה
i
{\displaystyle \displaystyle i}
תורמת
1
/
2
i
⋅
log
(
n
)
{\displaystyle \displaystyle 1/2^{i}\cdot \log(n)}
. נותר, לכן, לסכם
את
∑
i
=
1
log
(
log
(
n
)
)
[
1
/
2
i
⋅
log
(
n
)
]
{\displaystyle \displaystyle \sum _{i=1}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]}
:
∑
i
=
0
log
(
log
(
n
)
)
[
1
/
2
i
⋅
log
(
n
)
]
=
{\displaystyle \displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]=}
∑
i
=
0
log
(
log
(
n
)
)
[
1
/
2
i
]
⋅
log
(
n
)
=
{\displaystyle \displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}]\cdot \log(n)=}
Θ
(
1
)
⋅
log
(
n
)
=
{\displaystyle \displaystyle \Theta (1)\cdot \log(n)=}
Θ
(
log
(
n
)
)
{\displaystyle \displaystyle \Theta (\log(n))}
נוסחת נסיגה לבעיית "דג הסלמון"[ עריכה ]
T
(
n
)
{\displaystyle \displaystyle T(n)}
מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם
T
(
n
)
=
∑
i
=
1
n
−
1
[
T
(
i
)
]
+
Θ
(
n
)
{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)}
אז
T
(
n
)
=
Ω
(
1.5
n
)
{\displaystyle \displaystyle T(n)=\Omega (1.5^{n})}
.
הוכחה: נוכיח באינדוקציה שקיים
c
>
0
{\displaystyle \displaystyle c>0}
כך ש
T
(
n
)
≥
c
⋅
1.5
n
{\displaystyle \displaystyle T(n)\geq c\cdot 1.5^{n}}
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
n
−
1
{\displaystyle \displaystyle n-1}
, ונוכיח שהיא נכונה ל
n
{\displaystyle \displaystyle n}
. עפ"י נוסחת הנסיגה,
T
(
n
)
=
∑
i
=
1
n
−
1
[
T
(
i
)
]
+
Θ
(
n
)
≥
∑
i
=
1
n
−
1
[
T
(
i
)
]
+
c
′
⋅
n
{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)\geq \sum _{i=1}^{n-1}[T(i)]+c'\cdot n}
עבור
c
′
{\displaystyle \displaystyle c'}
כלשהו. לכן, עפ"י הנחת האינדוקציה,
T
(
n
)
≥
∑
i
=
1
n
−
1
[
c
⋅
1.5
i
]
+
c
′
⋅
n
{\displaystyle \displaystyle T(n)\geq \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n}
.
עפ"י הנוסחה לטור הנדסי ,
∑
i
=
1
n
−
1
[
c
⋅
1.5
i
]
+
c
′
⋅
n
=
{\displaystyle \displaystyle \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n=}
c
⋅
1.5
1
(
1.5
n
−
1
−
1
)
/
(
1.5
−
1
)
+
c
′
⋅
n
=
{\displaystyle \displaystyle c\cdot 1.5^{1}(1.5^{n-1}-1)/(1.5-1)+c'\cdot n=}
2
⋅
c
⋅
1.5
1
(
1.5
n
−
1
−
1
)
+
c
′
⋅
n
=
{\displaystyle \displaystyle 2\cdot c\cdot 1.5^{1}(1.5^{n-1}-1)+c'\cdot n=}
2
⋅
c
⋅
1.5
n
−
3
⋅
c
+
c
′
⋅
n
.
{\displaystyle \displaystyle 2\cdot c\cdot 1.5^{n}-3\cdot c+c'\cdot n.}
אם ניקח
c
<
c
′
/
3
{\displaystyle \displaystyle c<c'/3}
, אז הביטוי האחרון גדול מ
c
⋅
1.5
n
{\displaystyle \displaystyle c\cdot 1.5^{n}}
.
(בסיס האינדוקציה) היות ש
T
(
1
)
=
O
(
1
)
{\displaystyle \displaystyle T(1)=O(1)}
, אז
T
(
1
)
=
c
0
{\displaystyle \displaystyle T(1)=c_{0}}
, עבור
c
0
>
0
{\displaystyle \displaystyle c_{0}>0}
כלשהו. נפתור
T
(
1
)
=
c
0
≥
c
⋅
1.5
1
{\displaystyle \displaystyle T(1)=c_{0}\geq c\cdot 1.5^{1}}
, ונקבל
c
≤
c
0
/
1.5
{\displaystyle \displaystyle c\leq c_{0}/1.5}
.
האינדוקציה, לכן, נכונה עבור
0
<
c
<
min
{
c
0
/
1.5
,
c
′
/
3
}
{\displaystyle \displaystyle 0<c<\min\{c_{0}/1.5,c'/3\}}
, החל מ
n
=
1
{\displaystyle \displaystyle n=1}
.
נוסחת נסיגה לאיחוד קבוצות זרות על פי גודל[ עריכה ]
אנא הוכחה את המשפט הבא:
משפט:
פתרון
T
(
n
)
=
max
1
≤
i
≤
n
/
2
[
T
(
i
)
+
T
(
n
−
i
)
+
Θ
(
i
)
]
{\displaystyle \displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]}
הוא
O
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle O\left(n\cdot \log(n)\right)}
.
נוכיח באינדוקציה שקיים
c
>
0
{\displaystyle \displaystyle c>0}
כך ש(עבור
n
{\displaystyle \displaystyle n}
-ים מספיק גדולים)
T
(
n
)
≤
c
⋅
n
⋅
log
(
n
)
{\displaystyle \displaystyle T(n)\leq c\cdot n\cdot \log(n)}
.
(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,
T
(
n
)
=
max
i
=
1
,
…
,
n
/
2
[
T
(
i
)
+
T
(
n
−
i
)
+
Θ
(
i
)
]
≤
{\displaystyle \displaystyle T(n)=\max _{i=1,\ldots ,n/2}[T(i)+T(n-i)+\Theta (i)]\leq }
max
i
=
1
,
…
,
n
/
2
[
c
⋅
i
⋅
log
(
i
)
+
c
⋅
(
n
−
i
)
⋅
log
(
n
−
i
)
+
c
′
⋅
i
]
{\displaystyle \displaystyle \max _{i=1,\ldots ,n/2}[c\cdot i\cdot \log(i)+c\cdot (n-i)\cdot \log(n-i)+c'\cdot i]}
עבור קבוע
c
′
>
0
{\displaystyle \displaystyle c'>0}
כלשהו.
נגזור את הביטוי שבתוך ה
max
{\displaystyle \displaystyle \max }
, ונקבל
c
⋅
log
(
i
)
−
c
⋅
log
(
n
−
i
)
+
c
′
{\displaystyle \displaystyle c\cdot \log(i)-c\cdot \log(n-i)+c'}
נגזור את הביטוי פעם שניה, ונקבל ביטוי חיובי. מכאן ברור שמקסימום הביטוי הוא כאשר
i
=
n
/
2
{\displaystyle \displaystyle i=n/2}
.
כאשר
i
=
n
/
2
{\displaystyle \displaystyle i=n/2}
, אז
T
(
n
)
≤
2
⋅
c
⋅
n
/
2
⋅
log
(
n
/
2
)
+
c
′
=
{\displaystyle \displaystyle T(n)\leq 2\cdot c\cdot n/2\cdot \log(n/2)+c'=}
c
⋅
n
⋅
log
(
n
)
−
c
⋅
n
+
c
′
≤
{\displaystyle \displaystyle c\cdot n\cdot \log(n)-c\cdot n+c'\leq }
c
⋅
n
⋅
log
(
n
)
{\displaystyle \displaystyle c\cdot n\cdot \log(n)}
(בסיס האינדוקציה) נפתור:
(
c
⋅
i
⋅
log
(
i
)
)
|
i
=
2
,
3
=
O
(
1
)
{\displaystyle \displaystyle (c\cdot i\cdot \log(i))|^{i=2,3}=O(1)}
ונווכח שהדבר נכון עבור
c
{\displaystyle \displaystyle c}
גדול מספיק.
נוסחות נסיגה פשוטות[ עריכה ]
T
(
n
)
{\displaystyle \displaystyle T(n)}
מתארת את זמן הריצה של אלגוריתם כלשהו.
אנא הוכח שפתרון נוסחת הנסיגה
T
(
n
)
=
T
(
n
−
1
)
+
6
{\displaystyle \displaystyle T(n)=T(n-1)+6}
הוא
T
(
n
)
=
Θ
(
n
)
{\displaystyle \displaystyle T(n)=\Theta (n)}
.
אנא הוכח שפתרון נוסחת הנסיגה
T
(
n
)
=
T
(
n
−
1
)
+
6
⋅
n
{\displaystyle \displaystyle T(n)=T(n-1)+6\cdot n}
הוא
T
(
n
)
=
Θ
(
n
2
)
{\displaystyle \displaystyle T(n)=\Theta (n^{2})}
.
כרגיל, מותר לנו לקבוע ש
T
(
10
)
=
k
{\displaystyle \displaystyle T(10)=k}
עבור קבוע
k
{\displaystyle \displaystyle k}
כלשהו, וזאת משום ש
T
(
n
)
{\displaystyle \displaystyle T(n)}
מתארת את זמן הריצה של אלגוריתם.
נוכיח ש
T
(
n
)
=
O
(
n
)
{\displaystyle \displaystyle T(n)=O(n)}
. ליתר דיוק, נוכיח באינדוקציה שקיים
c
>
0
{\displaystyle \displaystyle c>0}
כך ש
T
(
n
)
≤
c
⋅
n
{\displaystyle \displaystyle T(n)\leq c\cdot n}
.
הוכחה: (בסיס האינדוקציה) עבור
n
=
10
{\displaystyle \displaystyle n=10}
, נקבל
T
(
10
)
=
k
≤
c
⋅
10
{\displaystyle \displaystyle T(10)=k\leq c\cdot 10}
, כלומר כל שצריך הוא לבחור
c
{\displaystyle \displaystyle c}
המקיים
c
≥
k
/
10
{\displaystyle \displaystyle c\geq k/10}
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
n
−
1
{\displaystyle \displaystyle n-1}
, ונוכיח שהיא נכונה עד (כולל)
n
{\displaystyle \displaystyle n}
. מהצבה בנוסחת הנסיגה, נקבל
T
(
n
)
=
T
(
n
−
1
)
+
6
≤
c
⋅
n
−
c
+
6.
{\displaystyle \displaystyle T(n)=T(n-1)+6\leq c\cdot n-c+6.}
עבור
c
≥
6
{\displaystyle \displaystyle c\geq 6}
, נקבל
T
(
n
)
≤
c
⋅
n
{\displaystyle \displaystyle T(n)\leq c\cdot n}
.
לסיכום, עבור
c
≥
max
{
k
/
10
,
6
}
{\displaystyle \displaystyle c\geq \max\{k/10,6\}}
, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.
נוכיח ש
T
(
n
)
=
Ω
(
n
)
{\displaystyle \displaystyle T(n)=\Omega (n)}
. ליתר דיוק, נוכיח באינדוקציה שקיים
c
>
0
{\displaystyle \displaystyle c>0}
כך ש
T
(
n
)
≥
c
⋅
n
{\displaystyle \displaystyle T(n)\geq c\cdot n}
.
הוכחה: (בסיס האינדוקציה) עבור
n
=
10
{\displaystyle \displaystyle n=10}
, נקבל
T
(
10
)
=
k
≥
c
⋅
10
{\displaystyle \displaystyle T(10)=k\geq c\cdot 10}
, כלומר כל שצריך הוא לבחור
c
{\displaystyle \displaystyle c}
המקיים
c
≤
k
/
10
{\displaystyle \displaystyle c\leq k/10}
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
n
−
1
{\displaystyle \displaystyle n-1}
, ונוכיח שהיא נכונה עד (כולל)
n
{\displaystyle \displaystyle n}
. מהצבה בנוסחת הנסיגה, נקבל
T
(
n
)
=
T
(
n
−
1
)
+
6
≥
c
⋅
n
−
c
+
6.
{\displaystyle \displaystyle T(n)=T(n-1)+6\geq c\cdot n-c+6.}
עבור
c
≤
6
{\displaystyle \displaystyle c\leq 6}
, נקבל
T
(
n
)
≥
c
⋅
n
{\displaystyle \displaystyle T(n)\geq c\cdot n}
.
לסיכום, עבור
c
≤
min
{
k
/
10
,
6
}
{\displaystyle \displaystyle c\leq \min\{k/10,6\}}
, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.
עלינו להוכיח שפתרון נוסחת הנסיגה
T
(
n
)
=
T
(
n
−
1
)
+
6
⋅
n
{\displaystyle \displaystyle T(n)=T(n-1)+6\cdot n}
הוא
T
(
n
)
=
Θ
(
n
2
)
{\displaystyle \displaystyle T(n)=\Theta (n^{2})}
. אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום
T
(
1
)
=
O
(
1
)
,
{\displaystyle \displaystyle T(1)=O(1),}
T
(
n
)
=
T
(
n
−
1
)
+
6
⋅
n
=
T
(
n
−
2
)
+
6
⋅
(
n
+
n
−
1
)
=
…
=
T
(
1
)
+
6
⋅
(
n
+
n
−
1
+
…
+
2
)
=
Θ
(
n
2
)
{\displaystyle \displaystyle T(n)=T(n-1)+6\cdot n=T(n-2)+6\cdot (n+n-1)=\ldots =T(1)+6\cdot (n+n-1+\ldots +2)=\Theta (n^{2})}
חסמים עליונים ותחתונים למספר נוסחאות נסיגה[ עריכה ]
אנא מצא חסמים עליונים ותחתונים (כלומר, מסוג
Ω
{\displaystyle \displaystyle \Omega }
ו
O
{\displaystyle \displaystyle O}
) טובים ככל האפשר לפונקציה
T
(
n
)
{\displaystyle \displaystyle T(n)}
בכל אחד מהסעיפים הבאים. (
T
(
n
)
{\displaystyle \displaystyle T(n)}
מתארת את זמן הריצה של אלגוריתם כלשהו.)
T
(
n
)
=
3
⋅
T
(
n
/
2
)
+
n
⋅
log
(
n
)
{\displaystyle \displaystyle T(n)=3\cdot T(n/2)+n\cdot \log(n)}
.
T
(
n
)
=
T
(
n
−
1
)
+
log
(
n
)
{\displaystyle \displaystyle T(n)=T(n-1)+\log(n)}
.
T
(
n
)
=
T
(
α
⋅
n
)
+
T
(
(
1
−
α
)
⋅
n
)
+
Θ
(
n
)
{\displaystyle \displaystyle T(n)=T(\alpha \cdot n)+T((1-\alpha )\cdot n)+\Theta (n)}
, כאשר
0
<
α
<
1
{\displaystyle \displaystyle 0<\alpha <1}
הוא קבוע כלשהו.
T
(
n
)
=
Θ
(
n
log
2
(
3
)
)
{\displaystyle \displaystyle T(n)=\Theta (n^{\log _{2}(3)})}
, עפ"י מקרה 1 של משפט המאסטר .
נפרוש את הנוסחה:
T
(
n
)
=
{\displaystyle \displaystyle T(n)=}
T
(
n
−
1
)
+
log
(
n
)
=
{\displaystyle \displaystyle T(n-1)+\log(n)=}
T
(
n
−
2
)
+
log
(
n
−
1
)
+
log
(
n
)
=
{\displaystyle \displaystyle T(n-2)+\log(n-1)+\log(n)=}
T
(
n
−
3
)
+
log
(
n
−
2
)
+
log
(
n
−
1
)
+
log
(
n
)
=
{\displaystyle \displaystyle T(n-3)+\log(n-2)+\log(n-1)+\log(n)=}
⋯
{\displaystyle \displaystyle \cdots }
∑
i
=
1
n
[
log
(
i
)
]
=
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=}
Θ
(
n
⋅
log
(
n
)
)
.
{\displaystyle \displaystyle \Theta (n\cdot \log(n)).}
(את המעבר האחרון ראינו בטורים שימושיים .)
נגדיר
α
′
=
1
−
α
{\displaystyle \displaystyle \alpha '=1-\alpha }
. בלי הגבלת הכלליות, נניח ש
α
<
α
′
{\displaystyle \displaystyle \alpha <\alpha '}
.
להלן עץ הפרישה המתקבל:
עץ הפרישה.
בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל
n
′
{\displaystyle \displaystyle n'}
, אז הילד השמאלי מתאים ל
α
n
′
{\displaystyle \displaystyle \alpha n'}
, והימני מתאים ל
α
′
n
′
{\displaystyle \displaystyle \alpha 'n'}
,. מכאן אפשר לראות שמסלולים שמאליים בעץ קצרים יותר ממסלולים ימניים, כי
α
′
=
1
−
α
{\displaystyle \displaystyle \alpha '=1-\alpha }
. לא כל הרמות בעץ מלאות, אם כן, מה שמקשה מעט על ניתוח הסיבוכיות. נגדיר כ
h
m
i
n
{\displaystyle \displaystyle h_{min}}
את אורך המסלול השמאלי ביותר, וכ
h
max
{\displaystyle \displaystyle h_{\max }}
את אורך המסלול הימני ביותר.
קל לראות שכל רמה מלאה בעץ תורמת
Θ
(
n
)
{\displaystyle \displaystyle \Theta (n)}
. הרמה הראשונה תורמת
Θ
(
n
)
{\displaystyle \displaystyle \Theta (n)}
; הרמה השניה תורמת
Θ
(
α
n
)
+
Θ
(
α
′
n
)
=
Θ
(
n
)
{\displaystyle \displaystyle \Theta (\alpha n)+\Theta (\alpha 'n)=\Theta (n)}
, הרמה השלישית תורמת
Θ
(
α
2
n
)
+
Θ
(
α
α
′
n
)
+
Θ
(
α
′
α
n
)
+
Θ
(
α
′
2
n
)
=
Θ
(
α
n
)
+
Θ
(
α
′
n
)
Θ
(
n
)
{\displaystyle \displaystyle \Theta (\alpha ^{2}n)+\Theta (\alpha \alpha 'n)+\Theta (\alpha '\alpha n)+\Theta (\alpha '^{2}n)=\Theta (\alpha n)+\Theta (\alpha 'n)\Theta (n)}
; וכו'. (אפשר להראות זאת פורמאלית באינדוקציה.)
אפשר לראות, לכן, ש
T
(
n
)
{\displaystyle \displaystyle T(n)}
חסומה מלמטה ע"י
h
m
i
n
⋅
Θ
(
n
)
{\displaystyle \displaystyle h_{min}\cdot \Theta (n)}
, וחסומה מלמעלה ע"י
h
max
⋅
Θ
(
n
)
{\displaystyle \displaystyle h_{\max }\cdot \Theta (n)}
. אבל היות ש
h
m
i
n
=
Θ
(
log
(
n
)
)
{\displaystyle \displaystyle h_{min}=\Theta (\log(n))}
וכן
h
max
=
Θ
(
log
(
n
)
)
{\displaystyle \displaystyle h_{\max }=\Theta (\log(n))}
, אז
T
(
n
)
=
Θ
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle T(n)=\Theta (n\cdot \log(n))}
.
נוסחת נסיגה שאיננה מתאימה למשפט המאסטר[ עריכה ]
T
(
n
)
{\displaystyle \displaystyle T(n)}
מתארת את זמן הריצה של אלגוריתם כלשהו, והיא פתרונה של נוסחת הנסיגה
T
(
n
)
=
a
⋅
T
(
n
b
)
+
f
(
n
)
{\displaystyle \displaystyle T(n)=a\cdot T\left({\frac {n}{b}}\right)+f(n)}
. בנוסחה זו,
a
{\displaystyle \displaystyle a}
מספר
שלם גדול ממש מ1,
b
{\displaystyle \displaystyle b}
מספר גדול ממש מ1, ו
f
(
n
)
{\displaystyle \displaystyle f(n)}
היא פונקציה
המקיימת
f
(
n
)
=
Θ
(
n
log
b
(
a
)
log
k
(
n
)
)
{\displaystyle \displaystyle f(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k}(n)\right)}
, עבור
k
{\displaystyle \displaystyle k}
שלם גדול ממש מ1.
אנא הוכח
T
(
n
)
=
Θ
(
n
log
b
(
a
)
log
k
+
1
(
n
)
)
{\displaystyle \displaystyle T(n)=\Theta \left(n^{\log _{b}(a)}\log ^{k+1}(n)\right)}
.
נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם
f
(
n
)
{\displaystyle \displaystyle f(n)}
. ברמה השניה יש
a
{\displaystyle \displaystyle a}
צמתים, וכל אחד מהם תורם
f
(
n
b
)
{\displaystyle \displaystyle f\left({\frac {n}{b}}\right)}
. ברמה ה
i
{\displaystyle \displaystyle i}
(בהנחה שהרמה הראשונה היא
ב
i
=
0
{\displaystyle \displaystyle i=0}
), יש
a
i
{\displaystyle \displaystyle a^{i}}
צמתים, וכל אחד מהם תורם
f
(
n
b
i
)
{\displaystyle \displaystyle f\left({\frac {n}{b^{i}}}\right)}
. אנו יודעים שגובה העץ הוא
h
=
Θ
(
log
b
(
n
)
)
{\displaystyle \displaystyle h=\Theta (\log _{b}(n))}
. נפשט:
∑
i
=
0
h
[
a
i
⋅
f
(
n
b
i
)
]
=
{\displaystyle \displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot f\left({\frac {n}{b^{i}}}\right)\right]=}
∑
i
=
0
h
[
a
i
⋅
Θ
(
(
n
b
i
)
log
b
(
a
)
⋅
log
k
(
n
b
i
)
)
]
=
{\displaystyle \displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot \Theta \left(\left({\frac {n}{b^{i}}}\right)^{\log _{b}(a)}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right)\right]=}
Θ
(
∑
i
=
0
h
[
a
i
⋅
n
log
b
(
a
)
b
i
⋅
log
b
(
a
)
⋅
log
k
(
n
b
i
)
]
)
=
{\displaystyle \displaystyle \Theta \left(\sum _{i=0}^{h}\left[a^{i}\cdot {\frac {n^{\log _{b}(a)}}{b^{i\cdot \log _{b}(a)}}}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=}
Θ
(
∑
i
=
0
h
[
a
i
⋅
n
log
b
(
a
)
a
i
⋅
log
k
(
n
b
i
)
]
)
=
{\displaystyle \displaystyle \Theta \left(\sum _{i=0}^{h}\left[a^{i}\cdot {\frac {n^{\log _{b}(a)}}{a^{i}}}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=}
Θ
(
n
log
b
(
a
)
∑
i
=
0
h
[
⋅
log
k
(
n
b
i
)
]
)
=
{\displaystyle \displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=}
Θ
(
n
log
b
(
a
)
∑
i
=
0
h
[
(
log
(
n
)
−
i
⋅
log
(
b
)
)
k
]
)
=
{\displaystyle \displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\left(\log(n)-i\cdot \log(b)\right)^{k}\right]\right)=}
Θ
(
n
log
b
(
a
)
log
(
b
)
k
∑
i
=
0
h
[
(
log
(
n
)
log
(
b
)
−
i
)
k
]
)
{\displaystyle \displaystyle \Theta \left(n^{\log _{b}(a)}\log(b)^{k}\sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]\right)}
נשים לב שעפ"י חסמי האינטגרלים לטורים ,
∑
i
=
0
h
[
(
log
(
n
)
log
(
b
)
−
i
)
k
]
=
Θ
(
log
k
+
1
(
n
)
)
{\displaystyle \displaystyle \sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]=\Theta \left(\log ^{k+1}(n)\right)}
.
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה קלה/שאלה
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה קלה/תשובה
נוסחת נסיגה מנחוסה[ עריכה ]
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה מנחוסה/שאלה
מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה מנחוסה/תשובה