נוסחת נסיגה עם שורש
עריכה
בנוסחת הנסיגה
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}
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)})}
משפט המאסטר .
נפרוש את הנוסחה:
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}
b
{\displaystyle \displaystyle b}
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}
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)}
נוסחת נסיגה קלה
עריכה
נוסחת נסיגה מנחוסה
עריכה
![{\displaystyle \displaystyle \sum _{i=1}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e87d48349de347f2d6cef46d2edb203a50ba662)
![{\displaystyle \displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93293e0cef32eb10049b63a0ac42739559c7c66f)
![{\displaystyle \displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}]\cdot \log(n)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ceaef1d9195ba8b0d37daaf0b318d69ef0b830bd)
![{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9236d8f52a4bdf6eef62d47a9cc894f85aeaf995)
![{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)\geq \sum _{i=1}^{n-1}[T(i)]+c'\cdot n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9a879a3bea72df50602f271bb55369b2547fb18)
![{\displaystyle \displaystyle T(n)\geq \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77f2be7be94eb270ef25742e33e82e4cbb719ab2)
![{\displaystyle \displaystyle \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e224fe8ab29eadf799ca576c8938570cb39f743d)
![{\displaystyle \displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef62acc75f5d5fb22b3af4c4aa5b098c7db57bda)
![{\displaystyle \displaystyle T(n)=\max _{i=1,\ldots ,n/2}[T(i)+T(n-i)+\Theta (i)]\leq }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ec88aa54ed45a752043aff3b854f56d8fbead77)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad6c84ec153276734558ddf097cc094b073f2417)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11350a4916c587a55c257aed7daf80732188d2d9)
![{\displaystyle \displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot f\left({\frac {n}{b^{i}}}\right)\right]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eab439c51a3b23135cbeee30163e405d3207a55c)
![{\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]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2795578a14f9ede3e89f1cdcd9bfcad97d13df4b)
![{\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)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5aa4f257249cf3e5bd79406ba207d6f38509a696)
![{\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)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46b7ceaaa3a640e93c7e255d699f935e2c8ac1b0)
![{\displaystyle \displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1f7e6e5ca983fe0b1145932bfcdf65cf84a2f8d)
![{\displaystyle \displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\left(\log(n)-i\cdot \log(b)\right)^{k}\right]\right)=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cbb9741bd8b01b57a6831512528a3754ac026a2)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96f14b54b2e5797d72edb36dbf77f62898bee061)
![{\displaystyle \displaystyle \sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]=\Theta \left(\log ^{k+1}(n)\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f06e735e375fb6254d69d64efed0b21420b37d4)