רקורסיות

צביקה ברגר

מרתון מבנה נתונים 2022

סיכום

צביקה ברגר

בס"ד

בס"ד

בס"ד

הפרד ומשול

בס"ד

מזה הפרד ומשול

• פרדיגמה לתכנון אלגורתמים המשתמשת ברקורסיה על מנת להפוך בעיה קשה לתתי בעיות קלות יותר.
• שלבים לפתרון הבעיה בשיטת הפרד ומשול:
• הפרד – פצל את הבעיה לתתי בעיות.
• ומשול – תפתור כל בעיה בפני עצמה.

​

• בחלק מהאלגוריתמים יש גם שלב:

מזג – חבר את התוצאות של כל תתי הבעיות.

בס"ד

למה זה טוב?

1. פתרון בעיות קשות – ניתן לקחת בעיה קשה ולפצל אותה לבעיות קטנות שיותר קל לפתור.
2. יעילות האלגוריתמים – בדרך כלל בבעיות קשות סיבוכיות זמן ריצה טובה (nlogn)o.
3. מקביליות – במימוש ניתן להריץ במקביל.

בס"ד

Divide and Conquer Algorithm

בס"ד

Divide and Conquer Algorithm

בס"ד

Merge Sort

הפרד – כל פעם תחלק את המערך לחצי.

ומשול – תמיין את החלק הקטן.

מזג – החזר את התשובה של כל תתי הבעיות.

​

בס"ד

הרעיון

בס"ד

בס"ד

ניתוח לשיעורין

בס"ד

בס"ד

מזה ניתוח לשיעורין

• ניתוח לשיעורין היא שיטה לניתוח אלגוריתמים, המחשבת סיבוכיות זמן ריצה של מספר פעולות ולא של פעולה בודדת.

בס"ד

למה זה טוב?

בהרבה מקרים לא אכפת לנו מה הסיבוכיות הריצה של פעולה בודדת אלא של רצף פעולות.

בס"ד

ניתוח לשיעורין

בס"ד

שיטת הצבירה

בס"ד

שיטת החיובים

בס"ד

שיטת הפוטנציאל

בס"ד

רשימת דילוגים

בס"ד

Array vs List

בס"ד

Array vs List

בס"ד

List

• Benefits:
• Easy to insert & delete in O(1) time.
• Don’t need to estimate total memory needed.
• Drawbacks:
• Hard to search in less than O(n) time.
• Hard to jump to the middle
• Skip Lists:
• fix these drawbacks

בס"ד

skip list

בס"ד

• Invented around 1990 by Bill Pugh.
• Generalization of sorted linked lists – so simple to implement
• Expected search time is O(log n).

Perfect skip list

בס"ד

Perfect skip list - find

בס"ד

Perfect skip list - find

בס"ד

Perfect skip list - insert

בס"ד

Perfect skip list - insert

בס"ד

Perfect skip list - delete

בס"ד

Perfect skip list - delete

בס"ד

עצי AVL

בס"ד

בס"ד

עצי AVL

בס"ד

עצים

בס"ד

עצים

בס"ד

B Tree

בס"ד

עצי B

בס"ד

עצים

בס"ד

עצים

בס"ד

עצים

בס"ד

Union Find

בס"ד

Union find

בס"ד

דוגמא שימוש

• דוגמא לשימוש ב-union find היא חישוב רכיבי קשירות תחת הוספת קשתות לגרף.

הגרף מתחיל בלי קשתות (וכל קדקוד הוא רכיב קשירות).

בכל פעם שמוסיפים קשת ייתכן ששני רכיבי קשירות יתמזגו ונרצה לאחד אותם.

​

בס"ד

עצים

בס"ד

מימוש עם רשימות מקושרות

בס"ד

ייעול 1

בס"ד

ייעול 1

בס"ד

ייעול 2

בס"ד

ייעול 2

בס"ד

ייעול 2

בס"ד

עצים

בס"ד

מימוש על ידי יער

בס"ד

כיווץ מסלולים

בס"ד

כיווץ מסלולים

בס"ד

Heap

בס"ד

ערימה בינארית

בס"ד

עצים

בס"ד

עצים

בס"ד

תכנות דינאמי

בס"ד

מזה תכנות דינאמי?

• תכנון דינאמי הוא שיטה לבניית אלגוריתם לפתרון בעיות שאינן ניתנות לפתרון יעיל בשיטת הפרד ומשול נאיבית.

​

​

​

ריצ'רד בלמן 1953.

​

בס"ד

עצים

בס"ד

פיבונאצ'י

​

​

• מה הסיבוכיות זמן הריצה של הפונקציה הבאה?

​

בס"ד

פיבונאצ'י

​

​

​

בס"ד

פיבונאצ'י

​

​

​

בס"ד

פיבונאצ'י

​

​

​

בס"ד

פיבונאצ'י

​

​

• מה סיבוכיות זמן הריצה של המימוש הזה של פיבונאצ'י?

בס"ד

פיבונאצ'י

​

​

• מה סיבוכיות זמן הריצה של המימוש הזה של פיבונאצ'י?

בס"ד

מיונים

בס"ד

מיונים מוכרים

​

• Bubble sort
• Merge sort
• Quick sort
• Insertion sort
• Heap sort

בס"ד

עצים

בס"ד

עצים

בס"ד

עצים

בס"ד

עצים

בס"ד