1 of 22

מבני נתונים��שיטת האב

בס"ד

צביקה ברגר

2 of 22

Merge Sort

​

​

  • מה זמן הריצה של הפונקציה?

​

​

​

​

​

בס"ד

3 of 22

Merge Sort

​

​

  • דוגמת הרצה:

​

​

​

​

​

בס"ד

4 of 22

Merge Sort

​

​

  • מה זמן הריצה של הפונקציה?

​

​

​

​

​

בס"ד

5 of 22

שיטת האב

​

​

  • כדי לחשב זמן ריצה של פונקציה רקורסיבית נשתמש בשיטת האב.
    • נפתח נוסחא שמתארת את הפונקציה מהצורה:

​

​

​

​

​

בס"ד

6 of 22

סיבוכיות - שיטת האב

​

​

  • נסתכל על הפונקציה :

​

​

בס"ד

7 of 22

שיטת האב

​

​

​

​

בס"ד

8 of 22

שיטת האב

​

​

​

​

בס"ד

9 of 22

שיטת האב

​

​

​

​

בס"ד

10 of 22

שיטת האב

​

​

​

​

בס"ד

11 of 22

שיטת האב

​

​

​

​

בס"ד

12 of 22

תרגיל 1

בס"ד

13 of 22

תרגיל 2

בס"ד

14 of 22

פתרון

בס"ד

15 of 22

תרגיל 3

בס"ד

16 of 22

פתרון

בס"ד

17 of 22

תרגיל 4

בס"ד

18 of 22

פתרון

בס"ד

n^2 log(n)

1. n^3

2. n^2 log(n)

3. n^3

4. n^2

19 of 22

תרגיל 5

בס"ד

20 of 22

תרגיל 6

בס"ד

21 of 22

תרגיל 7

בס"ד

22 of 22

שאלות?

בס"ד