Data Structures – Recitation 6
Shay Golan
1
ניתוח לשיעורין�Amortized Analysis
2
מחסנית משודרגת
MultiPop(S)
While (S.isEmpty()==false)
S.Pop();
3
מחסנית משודרגת
4
מחסנית משודרגת
5
ניתוח לשיעורין
6
ניתוח לשיעורין
7
שיטת הצבירה
8
שיטת הצבירה
9
שיטת הצבירה – מחסנית משודרגת
10
שיטת הצבירה – מחסנית משודרגת
11
דוגמה נוספת – קידום מונה בינארי
12
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
3
4
5
6
קידום מונה בינארי
13
קידום מונה בינארי
14
דוגמה נוספת – מערך דינמי
15
שיטה א'
16
שיטה ב'
17
1
3
4
6
1
3
1
3
4
6
7
12
15
17
1
3
4
6
7
12
15
17
20
25
27
4
שיטה ב'
18
שיטת החיובים
19
שיטת החיובים – "בנק"
20
שיטת החיובים למחסנית
21
| עלות אמיתית | עלות לשיעורין |
Push | 1 | 2 |
Pop | 1 | 0 |
MultiPop | כמספר האיברים במחסנית | 0 |
שיטת החיובים למחסנית
22
דוגמה נוספת – קידום מונה בינארי
23
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
3
4
5
6
קידום מונה בינארי
24
מונה בינארי
25
מונה בינארי
26
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
3
4
5
6
מונה בינארי
27
מערך דינמי
28
מערך דינמי
29
1
3
4
6
1
3
4
6
7
12
15
17
1
3
4
6
7
12
15
17
20
25
27
מערך דינמי - הבחנות
30
שיטת הפוטנציאל
31
שיטת הפוטנציאל
32
33
שיטת הפוטנציאל
34
עלות אמיתית
הפרש הפוטנציאלים
שיטת הפוטנציאל
35
שיטת הפוטנציאל
36
מחסנית
37
מערך דינמי
38
1
3
4
6
7
12
15
17
20
25
27
מערך דינמי - הכנסה
39
מערך דינמי - הכנסה
40
מערך דינמי מלא
41
מערך דינמי מלא
42
ניתוח-הכנסה
43
ניתוח - הוצאה
44
דה-אמורטיזציה�Deamortization
45
דה-אמורטיזציה למערך דינמי
46
מערך דינמי –דה אמורטיזציה
47
1
3
4
6
1
3
1
3
4
6
7
12
15
17
1
3
4
6
7
12
15
17
20
25
27
4
1
3
4
6
7
12
A
B
A
B
A
B
A
B
מערך דינמי –דה אמורטיזציה
48
מערך דינמי –דה אמורטיזציה
49