לפי FIFO
לפי - LIFO
מיונים מבוססי השוואה
מיון ערימה – Heap Sort
סיבוכיות זמן ריצה
O(nlog(n))
הפונקציה העיקרית:
HeapSort(A)
Build-Heap(A)
for i <- length[A] downto 2
do exchange A[1] <-> A[i]
heap-size[A] <- heap-size[A]-1
Heapify(A,1)
פונקציות עזר:
(Heapify(A,i
הבן השמאלי של צומת l <- LEFT(i) // i
הבן הימני של צומת r <- RIGHT(i) //i
[if l <= heapsize[A] and A[l] > A[i
then largest <- l
else largest <- i
[if r<=heapsize[A] and A[r] > A[largest
then largest <- r
if largest != i
[then exchange A[i] <-> A[largest
Heapify(A,largest)
Build-Heap(A)
heap_size[A] <- length[A]
for i <- length[A]/2 Downto 1
do Heapify(A,i)
מיון ערימה עובד בצורה הבאה:
(נבנה ערימת מקסימום ממערך לא ממוין (זמן ריצה:
ידוע שהאיבר המקסימלי במערך נמצא במקום הראשון בערימה, נחליף אותו עם האיבר האחרון בערימה (כי לאחר המיון הוא צריך להיות במקום האחרון במערך).
נקטין את גודל הערימה באחד.
נבצע על האיבר הראשון בערימה MaxHeapify כדי לתקן את הערימה.
נבצע את שלבים 2 עד 4 עבור כל איברי המערך בלולאה (מהסוף להתחלה)
קיבלנו מערך ממוין.
הגדרות
פעולות המוגדרות על ערימה
שמירת תכונת הערימה - Heapify
מחיקת איבר בעל מפתח מקסימאלי בערימת מקסימום - Heap-Extract-Max
החזרת איבר בעל מפתח מקסימלי בערימת המקסימום - Max-Heap
הכנסת איבר חדש – Max-Heap-Insert
יוצרת ערימה ממערך קלט בלתי ממויין - Heap-Max-Build
מס' העלים בערימה
בערימה בת n איברים יש n/2(ערך עליון) עלים
גובה של ערימה
גובה של ערימה בת n איברים הוא ((O(log(n
ערימה מקיימת את תכונת הערימה
לכל צומת i מתקיים:
[A[parent(i)] ≥ A[i ערימת מקסימום
[A[parent(i)] ≤ A[i ערימת מינמום
למערך A המייצג ערימה שני
מאפיינים:
גודל הערימה - [heap-size[A
גודל המערך – [length[A
בהינתן אינדקס i של הצומת
right(i)
return (2*i+1)
(parent(i
(ערך תחתון)return i/2
left(i)
return (2*i)
שורש העץ -[1]A
ערימה (בינארית) הוא עצם מטיפוס מערך, שניתן לראותו כעץ
בינארי שלם. לכל צומת בעץ מתאים איבר במערך שבו מאוחסן
הערך שמכיל הצומת
מיון מיזוג -Marge Sort
מיון מיזוג הוא אלגוריתם מיון רקורסיבי קל למימוש המתבסס על קלות מיזוגם של מערכים ממוינים
mergesort(Array m)
{
if length(m) ≤ 1
return m
else
{
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = mergesort(left)
right = mergesort(right)
result = merge(left, right)
return result
}
}
מיון-מיזוג עובד בצורה הבאה:
מיין-מזג n איברים
אם n=1 (המערך של איבר אחד ממילא ממוין) חזור
מיין-מזג את n/2 האברים הראשונים
מיין-מזג את n/2 האברים האחרונים
מזג את 2 תוצאות המיון
ננסה לחשב תחילה את מספר הפעמים שמתבצעת פעולת המיזוג. הפעולה מתבצעת בכל קריאה לפונקציה "מיון-מיזוג".
הקריאה הראשונה תמזג בין שני חצאי מערכים בגודל \ n/2 (סה"כ \ n איברים, סיבוכיות זמן ריצה \ (O(n.
לפני-כן הקריאה הראשונה קוראת פעמיים למיון-מיזוג, פעם אחת עבור חצי המערך הראשון ופעם שנייה עבור חצי המערך השני.
בכל קריאה יתבצע מיזוג של שני חצאי מערכים בגודל \ n/4 , סה"כ מדובר ב-4 מערכים ולכן יש סה"כ \ n איברים שיתמזגו ושוב סיבוכיות זמן הריצה הכוללת היא \ (O(n.
האלגוריתם ימשיך עד אשר כל המערכים יהיו בגודל 1 ואז נמזג אותם זוג-זוג, עדיין מדובר ב-\ n איברים ולכן סיבוכיות זמן הריצה של כל פעולות המיזוג יחד היא \ (O(n.
נסתכל בכל פעם רק על חלק אחד של המערך המפוצל, נתחיל במערך הגדול ונשאר עם מערך בגודל \ n/2 ואז נמשיך להתבונן במערך בגודל \ n/4 וכן הלאה, עד אשר נגיע למערך בגודל 1. בכל שלב מתבצע מיזוג שזמן ריצתו \ (O(n , נותר רק לספור כמה שלבים כאלו יש.
כפי שנאמר קודם, בכל פעם אנו שולחים למיון-מיזוג מערך שגודלו חצי מהמערך הקודם.
לאחר קריאה אחת יהיה גודל המערך n\2, לאחר שתי קריאות יהיה גודלו n\4 וכן הלאה. התהליך ייגמר כאשר גודל המערך הינו 1.
אם התהליך כולו יימשך k פעמים, יהיה גודל המערך n\2^k.
אנו דורשים שגודל זה יהיה 1 ולכן נדרוש \n\2^k = 1.
נוציא log משני אגפי המשוואה ונקבל כי (k = log(n.
קבלנו שמתרחשות (log(n פעולות מיזוג שסיבוכיות זמן הריצה של כל אחת מהן היא (O(n.
סה"כ סיבוכיות זמן הריצה של האלגוריתם היא, אם כן, ((O(nlog(n.
מיון מהיר-Quick Sort
חישוב סיבוכיות זמן ריצה
המקרה הממוצע – על מנת לקבל את המקרה הממוצע, נבחר את הpivot בצורה אקראית בכל קריאה לpartition וכך תהיה הסתברות שווה לכל אחד מאיברי המערך להיבחר להיות הpivot. זמן הריצה במקרה הזה הוא ((O(nlog(n.
המקרה הגרוע ביותר – המקרה הגרוע ביותר הוא כאשר ה pivot הוא האיבר המינימלי/המקסימלי ואז נוכל לנתח את זמן הריצה באמצעות הנוסחה הרקורסיבית:T(n)=2T(n-1)+O(n) ולאחר שנפתור אותה נקבל (O(n^2.
המקרה הטוב ביותר – המקרה הטוב ביותר הוא כאשר הpivot הוא איבר החציון, ואז ניתן לנתח את זמן הריצה של המיון באמצעות הנוסחה הרקורסיבית:(T(n)=2T(n/2)+O(n , ולאחר שנפתור את הנוסחה נקבל ((O(nlog(n.
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
מיון-מהיר עובד בצורה הבאה:
בהינתן סדרת איברים, בחר איבר מהסדרה באקראי (נקרא: pivot, או "איבר ציר").
סדר את כל האיברים כך שהאיברים הגדולים מאיבר הציר יופיעו אחרי האיברים הקטנים מאיבר הציר.
באופן רקורסיבי, הפעל את האלגוריתם על סדרת האיברים הגדולים יותר ועל סדרת האיברים הקטנים יותר
תנאי העצירה של האלגוריתם הוא כאשר ישנו איבר אחד, ואז האלגוריתם מודיע כי הסדרה ממוינת.
מיונים בזמן לינארי
מיון מניה – Counting Sort
תכונות
מיון יציב
סיבוכיות זמן ריצה:
(טריוואלי שיהיה (O(n
אם לא הבנת זאת לבד
חזור לסדרי גודל)
נשים לב שמיון ספירה מורכב למעשה משתי לולאות באורך n שתי לולאות באורך k.
לכן (O(n+k ואז נשים לב ש-k הוא קבוע ולכן פולינום מדרגה 1 ומכך שזמן הריצה שווה ל-(O(n.
הנחה על הקלט:
איברי הקלט הם מספרים שלמים בתחום [0-k]
.הערה: במידה ולא בתחום זה, אז ניתן למצוא פונקציה שתקיים תחום זה
מיון מניה עובד בצורה הבאה:
לכל איבר x, נספור את כמות האיברים שקטנים/שווים לו וכך נדע איפה הוא צריך להיות במערך הסופי.
פסודו קוד
CountingSort(A[],k,B[])
// A and B are arrays of size n
// B is the output array
Create new array C of size k+1
for i=0 to k
C[i] = 0
for j=1 to n
C[A[j]] = C[A[j]+1]
for i=1 to k
C[i] = C[i] + C[i-1]
for j=n downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
מיון בסיס – Radix Sort
אם נשתמש במיון מניה כמיון משני אז ((O(d(n+k , כאשר d מס' הספרות ו-k הבסיס
של כל ספרה.
אם d קבוע ו-(k=O(n אז נקבל זמן ריצה ליניארי.
O(n)
אולגריתם
הנחה על הקלט:
איברי הקלט הם מספרים שלמים בני d ספרות (אם מס' הספרות של איברי הקלט אינו שווה בכולם, נקח את המקסימלי מביניהם).
פסודו קוד:
RadixSort(A[],d)
for i=1 to d
use counting sort to sort array A on digit i
מיון בסיס עובד בצורה הבאה:
כדי שהמיון יעבוד, המיון הפנימי שנשתמש בו חייב להיות מיון יציב.
במיון זה נשתמש במיון אחר (חייב להיות מיון יציב) ונמיין איתו את המערך ע"פ כל אחת מהספרות, נתחיל מספרת האחדות ונמשיך לעשרות, למאות וכו'
עקרון הפרד ומשול:
משול:
חיבור כל הפתרונות הקטנים וקבלת הפתרון הדרוש
הפרד:
חילוק הבעיה הגדול לתתי קבוצות קטנות יותר
ופתירת הבעיה עבור כל הקבוצות קטנות
סדרי גודל
דרך יעילה לפתרון
בעיות סיבוכיות של אולגריתימים היא באמצעות סדרי גודל,
חסמים אסימפטוטים המביעים את יחס הגודל בין פונקציות
ובאמצעותן ניתן לנחש את הפונקציה החוסמת מלמטה או למעלה ונחסום את הפונקציה המגדירה את זמן הריצה
של האולגריתם ובכך נקבל את המקסימום או המינמום של הפעולות אותן תבצע התוכנית בזמן הריצה שלה ובמידה וקיבלנו שהמינמום והמקסימום שווים אז ניתן לקבוע שהפונקציה היא בדיוק מספר הפעולות אותן מבצעת התוכנית
3.f(n) = Ω(g(n))
עבור שתי פונקציות f(n), g(n) נאמר שאם קיימים קבועים חיוביים c, n0, כך שעבור n≥n0 מתקיים:
0 ≤ cg(n) ≤ f(n)
2.f(x)=Θ(g(n))
עבור שתי פונקציות (g(n), f(n נאמר שאם קיימים שלושה קבועים חיוביים
c1, c2, n0 כך שלכל n≥n0 מתקיים:
(c1g(n) ≤ f(n) ≤ c2g(n
1.f(n)=O(g(n))
אם עבור שתי פונקציות (f(n), g(n נאמר ש- ((f(n) = O(g(n אם קיימים קבועים חיוביים c, n0 כך שלכל n≥n0 מתקיים:
(f(n)≤C*g(n
נוסחאות נסיגה- ניתן לפתור נוסחאות נסיגה בכמה שיטות:
שיטת העץ:
בשיטת עצי רקורסיה נשתמש כאשר יש יותר מפיצול אחד ברקורסיה, והפיצולים לא שווים. כלומר, למשל:
T(n) = 3T(n/8) + 7T(n/12) + 4n
בשיטה זו אנחנו פשוט מציירים את עץ הרקורסיה, ומציירים למעשה "עץ קריאות". בנוסף, לכל קריאה אנחנו מחשבים את כמות העבודה שבוצעה באותה הקריאה (לדוגמא, עבור הנוסחא הנתונה, הקריאה (n(T קוראת לשתי קריאות רקורסיביות ־ 3 פעמים (8/n(T ,ו־7 פעמים (12/n(T .בנוסף, הקריאה מבצעת 4n עבודה). לאחר שציירנו את הקריאות, ואת העבודה שבוצעה בכל קריאה, מחשבים את כמות העבודה הכללית בכל רמה בעץ.
אינדוקציה:
בשיטה זו, לא נמצא פתרון מפורש לפונקציה. שיטה זו תעזור לנו להכיח חסם תחתון/עליון/הדוק לפונקציה הראשית יש "לנחש" לאיזו מחלקה הפונקציה שייכת (או שהטענה ידועה), וכל שאנו רוצים הוא להוכיח שאכן זהו
החסם. שיטה זו היא בפשטות... אינדוקציה
משפט האב:
בהנתן נוסחת נסיגה מהצורה: (T(n) = aT(n/b) + f(n
ו- 0<ε כלשהו
מקרה ג'
,(f(n)=Ω(n^log(b)a +ε
((a*f(n/b)=O(f(n
אזי
((T(n)=Θ(f(n
מקרה ב'
(f(n)=O(n^log(b)a
אזי
(T(n)=Θ((n^log(b)a)*logn
מקרה א'
f(n)=O(n^log(b)a -ε)
אזי
(T(n)=Θ(n^(log(b)a
מבני נתונים
יעילות של מבני נתונים ואולגריתימים
קריטריונים לבדיקה
תקשורת
זיכרון
זמן ריצה (המרכזי ביותר בו נעסוק בקורס באופן נרחב)
מוגדר ע"י מס' הפעולות אותן מבצע הקוד
תור
שתי מחסניות
רשימות דו מקושרות
מערך
isEmpty-בודק האם התור ריקה
פסודו קוד:
()IsEmpty
(return (back==null
Top-האיבר האחרון בתור
Init-אתחול התור
פסודו קוד:
()INIT
l. # A list
Dequeue- הוצאה של איברים לתור
פסודו קוד:
(Dequeue(q
(v = Back(q.l
(Delete-Back(q.l
return v
Enqueue- הכנסה של איברים לתור
ישום על רשימה מקושרת דו כיוונית
פסודו קוד:
(Enqueue(q, v
(Insert-Front(q.l, v
מחסנית
פעולות על המחסנית
ניתן לקיים חוקיות זאת באמצעות:
רשימות דו מוקשרות
סיבוכיות ריצה:(O(1
רשימות מקושרות
סיבוכיות ריצה:(O(n
isEmpty-בודק האם המחסנית ריקה
פסודו קוד:
()StackIsEmpty
(return (top==0
Top-האיבר האחרון במחסנית
Init-אתחול המחסנית
פסודו קוד:
()SteckINIT
TOP=0
Pop- הוצאה של איברים מהמחסנית
פסודו קוד:
()Pop
if (StackIsEmpty):error-overflow
else
[tmp=S[top
--top
return tmp
Push- הכנסה של איברים למחסנית
ישום
פסודו קוד:
(Push(x
if (StackIsEmpty):error-overflow
else
top++
S[top]=x
מתנהג כמו מחסנית של רובה
מיונים
חציונים וערכי מיקום
דרכים למימוש:
אולגריתם 4:
חציון
בהנתן n איברים החציון הוא האיבר שקיימים n/2 ערכים קטנים ממנו ו-n/2 ערכים גדולים ממנו
סיבוכיות זמן ריצה:
מי בהכרח קטן מהפיבוט?
מחצית מקבוצת חציוני החמישיות
לכל חציון של חמישיה עוד 2 איברים קטנים ממנו
מי בהכרח גדול מהפיבוט?
מחצית מקבוצת חציוני החמישויות
לכל חציון שני איברים הגדולים ממנו
לכל הפחות:
3n/10
נסו לפתור בעזרת אינדוקציה את הנוסחא הרקוסיבית
T(n)=O(n)
לכל היותר:
7n/10
חלק את A לחמישיות
מצא את החציון של כל חמישיה
מצא את החציון של כל החציונים שמצאנו קודם (ברקורסיה)
השתמש בחציון החציונים בתור פיבוט
שימוש באולגריתם עזר המחלק את המערך באופן מאוזן
אולגריתם 3:
נחלק את המערך באמצעות הpartition
נחפש בתת מערך עבור פיבוט
יחי אינדקס שאליו הגיע הפיבוט
אם P קטן מ-K:
המשך לחפש בתת מערך ימין
אם P גדול מ-K:
המשך לחפש את k בתת מערך שמאל
אם p=k החזר [A[p
אולגריתם 2:
אם k=1:
מעבר אחד על A
ומציאת המינ'
אם k=2:
אפשר בשני מעברים על
או בשני משתנים
אולגריתם 1:
מיונים מבוססי השוואה (O(nlogn
זמן ריצה: (O(nlogn
מיין את A
החזר את [A[K
קלט/פלט
פלט: האיבר ה-k בגודלו
קלט: מערך לא ממוין של A עם n מספרים ומספר k בין 1 ל-n
