מבני נתונים

קלט/פלט

קלט: מערך לא ממוין של A עם n מספרים ומספר k בין 1 ל-n

פלט: האיבר ה-k בגודלו

דרכים למימוש:

אולגריתם 1:

מיין את A

החזר את [A[K

מיונים מבוססי השוואה (O(nlogn

זמן ריצה: (O(nlogn

אולגריתם 2:

אם k=1:
מעבר אחד על A
ומציאת המינ'

אם k=2:
אפשר בשני מעברים על
או בשני משתנים

אולגריתם 3:

נחלק את המערך באמצעות הpartition

נחפש בתת מערך עבור פיבוט

יחי אינדקס שאליו הגיע הפיבוט

אם p=k החזר [A[p

אם P גדול מ-K:
המשך לחפש את k בתת מערך שמאל

אם P קטן מ-K:
המשך לחפש בתת מערך ימין

אולגריתם 4:

שימוש באולגריתם עזר המחלק את המערך באופן מאוזן

חלק את A לחמישיות

מצא את החציון של כל חמישיה

מצא את החציון של כל החציונים שמצאנו קודם (ברקורסיה)

השתמש בחציון החציונים בתור פיבוט

אם p=k החזר [A[p

אם P גדול מ-K:
המשך לחפש את k בתת מערך שמאל

אם P קטן מ-K:
המשך לחפש בתת מערך ימין

סיבוכיות זמן ריצה:

מי בהכרח גדול מהפיבוט?

מחצית מקבוצת חציוני החמישויות

לכל חציון שני איברים הגדולים ממנו

לכל היותר:
7n/10

לכל הפחות:
3n/10

נסו לפתור בעזרת אינדוקציה את הנוסחא הרקוסיבית

T(n)=O(n)

מי בהכרח קטן מהפיבוט?

מחצית מקבוצת חציוני החמישיות

לכל חציון של חמישיה עוד 2 איברים קטנים ממנו

לכל היותר:
7n/10

לכל הפחות:
3n/10

חציון

בהנתן n איברים החציון הוא האיבר שקיימים n/2 ערכים קטנים ממנו ו-n/2 ערכים גדולים ממנו

מתנהג כמו מחסנית של רובה

פעולות על המחסנית

Push- הכנסה של איברים למחסנית

ישום

פסודו קוד:
(Push(x
if (StackIsEmpty):error-overflow
else
top++
S[top]=x

Pop- הוצאה של איברים מהמחסנית

ישום

פסודו קוד:
()Pop
if (StackIsEmpty):error-overflow
else
[tmp=S[top
--top
return tmp

Init-אתחול המחסנית

ישום

פסודו קוד:
()SteckINIT
TOP=0

Top-האיבר האחרון במחסנית

isEmpty-בודק האם המחסנית ריקה

ישום

פסודו קוד:
()StackIsEmpty
(return (top==0

ניתן לקיים חוקיות זאת באמצעות:

רשימות מקושרות

סיבוכיות ריצה:(O(n

סיבוכיות ריצה:(O(1

פעולות על המחסנית

Enqueue- הכנסה של איברים לתור

ישום על רשימה מקושרת דו כיוונית

פסודו קוד:
(Enqueue(q, v
(Insert-Front(q.l, v

Dequeue- הוצאה של איברים לתור

ישום על רשימה מקושרת דו כיוונית

פסודו קוד:
(Dequeue(q
(v = Back(q.l
(Delete-Back(q.l
return v

Init-אתחול התור

ישום על רשימה מקושרת דו כיוונית

פסודו קוד:
()INIT
l. # A list

Top-האיבר האחרון בתור

isEmpty-בודק האם התור ריקה

ישום על רשימה מקושרת דו כיוונית

פסודו קוד:
()IsEmpty
(return (back==null

ניתן לקיים חוקיות זאת באמצעות:

רשימות מקושרות

סיבוכיות ריצה:(O(n

מערך

סיבוכיות ריצה:(O(n

סיבוכיות ריצה:(O(1

שתי מחסניות

סיבוכיות ריצה:(O(n

קריטריונים לבדיקה

זמן ריצה (המרכזי ביותר בו נעסוק בקורס באופן נרחב)

מוגדר ע"י מס' הפעולות אותן מבצע הקוד

זיכרון

תקשורת

מקרה א'

f(n)=O(n^log(b)a -ε)

אזי

(T(n)=Θ(n^(log(b)a

מקרה ב'

(f(n)=O(n^log(b)a

אזי

(T(n)=Θ((n^log(b)a)*logn

מקרה ג'

,(f(n)=Ω(n^log(b)a +ε
((a*f(n/b)=O(f(n

אזי

((T(n)=Θ(f(n

אם עבור שתי פונקציות (f(n), g(n נאמר ש- ((f(n) = O(g(n אם קיימים קבועים חיוביים c, n0 כך שלכל n≥n0 מתקיים:


(f(n)≤C*g(n

עבור שתי פונקציות (g(n), f(n נאמר שאם קיימים שלושה קבועים חיוביים
c1, c2, n0 כך שלכל n≥n0 מתקיים:

(c1g(n) ≤ f(n) ≤ c2g(n

עבור שתי פונקציות f(n), g(n) נאמר שאם קיימים קבועים חיוביים c, n0, כך שעבור n≥n0 מתקיים:

0 ≤ cg(n) ≤ f(n)

אולגריתם

מיון בסיס עובד בצורה הבאה:

כדי שהמיון יעבוד, המיון הפנימי שנשתמש בו חייב להיות מיון יציב.

במיון זה נשתמש במיון אחר (חייב להיות מיון יציב) ונמיין איתו את המערך ע"פ כל אחת מהספרות, נתחיל מספרת האחדות ונמשיך לעשרות, למאות וכו'

פסודו קוד:

RadixSort(A[],d)
for i=1 to d
use counting sort to sort array A on digit i

הנחה על הקלט:
איברי הקלט הם מספרים שלמים בני d ספרות (אם מס' הספרות של איברי הקלט אינו שווה בכולם, נקח את המקסימלי מביניהם).

סיבוכיות זמן ריצה:

אם נשתמש במיון מניה כמיון משני אז ((O(d(n+k , כאשר d מס' הספרות ו-k הבסיס
של כל ספרה.
אם d קבוע ו-(k=O(n אז נקבל זמן ריצה ליניארי.

O(n)

אולגריתם

פסודו קוד

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

מיון מניה עובד בצורה הבאה:

לכל איבר x, נספור את כמות האיברים שקטנים/שווים לו וכך נדע איפה הוא צריך להיות במערך הסופי.

הנחה על הקלט:
איברי הקלט הם מספרים שלמים בתחום [0-k]
.הערה: במידה ולא בתחום זה, אז ניתן למצוא פונקציה שתקיים תחום זה

סיבוכיות זמן ריצה:
(טריוואלי שיהיה (O(n
אם לא הבנת זאת לבד
חזור לסדרי גודל)

נשים לב שמיון ספירה מורכב למעשה משתי לולאות באורך n שתי לולאות באורך k.
לכן (O(n+k ואז נשים לב ש-k הוא קבוע ולכן פולינום מדרגה 1 ומכך שזמן הריצה שווה ל-(O(n.

תכונות

מיון יציב

אולגריתם

מיון-מהיר עובד בצורה הבאה:

בהינתן סדרת איברים, בחר איבר מהסדרה באקראי (נקרא: pivot, או "איבר ציר").

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

באופן רקורסיבי, הפעל את האלגוריתם על סדרת האיברים הגדולים יותר ועל סדרת האיברים הקטנים יותר

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

פסודו קוד

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 הוא איבר החציון, ואז ניתן לנתח את זמן הריצה של המיון באמצעות הנוסחה הרקורסיבית:(T(n)=2T(n/2)+O(n , ולאחר שנפתור את הנוסחה נקבל ((O(nlog(n.

המקרה הגרוע ביותר – המקרה הגרוע ביותר הוא כאשר ה pivot הוא האיבר המינימלי/המקסימלי ואז נוכל לנתח את זמן הריצה באמצעות הנוסחה הרקורסיבית:T(n)=2T(n-1)+O(n) ולאחר שנפתור אותה נקבל (O(n^2.

המקרה הממוצע – על מנת לקבל את המקרה הממוצע, נבחר את הpivot בצורה אקראית בכל קריאה לpartition וכך תהיה הסתברות שווה לכל אחד מאיברי המערך להיבחר להיות הpivot. זמן הריצה במקרה הזה הוא ((O(nlog(n.

חישוב סיבוכיות זמן ריצה

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

הקריאה הראשונה תמזג בין שני חצאי מערכים בגודל \ 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.

אולגריתם

מיון-מיזוג עובד בצורה הבאה:

מיין-מזג n איברים

אם n=1 (המערך של איבר אחד ממילא ממוין) חזור

מיין-מזג את n/2 האברים הראשונים

מיין-מזג את n/2 האברים האחרונים

מזג את 2 תוצאות המיון

פסודו קוד

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
}
}

הגדרות

ערימה (בינארית) הוא עצם מטיפוס מערך, שניתן לראותו כעץ
בינארי שלם. לכל צומת בעץ מתאים איבר במערך שבו מאוחסן
הערך שמכיל הצומת

שורש העץ -[1]A

בהינתן אינדקס i של הצומת

left(i)
return (2*i)

(parent(i
(ערך תחתון)return i/2

right(i)
return (2*i+1)

למערך A המייצג ערימה שני
מאפיינים:

גודל המערך – [length[A

גודל הערימה - [heap-size[A

ערימה מקיימת את תכונת הערימה
לכל צומת i מתקיים:

[A[parent(i)] ≤ A[i ערימת מינמום

[A[parent(i)] ≥ A[i ערימת מקסימום

גובה של ערימה
גובה של ערימה בת n איברים הוא ((O(log(n

מס' העלים בערימה
בערימה בת n איברים יש n/2(ערך עליון) עלים

פעולות המוגדרות על ערימה

יוצרת ערימה ממערך קלט בלתי ממויין - Heap-Max-Build

הכנסת איבר חדש – Max-Heap-Insert

החזרת איבר בעל מפתח מקסימלי בערימת המקסימום - Max-Heap

מחיקת איבר בעל מפתח מקסימאלי בערימת מקסימום - Heap-Extract-Max

שמירת תכונת הערימה - Heapify

אולגריתם

מיון ערימה עובד בצורה הבאה:

(נבנה ערימת מקסימום ממערך לא ממוין (זמן ריצה:

ידוע שהאיבר המקסימלי במערך נמצא במקום הראשון בערימה, נחליף אותו עם האיבר האחרון בערימה (כי לאחר המיון הוא צריך להיות במקום האחרון במערך).

נקטין את גודל הערימה באחד.

נבצע על האיבר הראשון בערימה MaxHeapify כדי לתקן את הערימה.

נבצע את שלבים 2 עד 4 עבור כל איברי המערך בלולאה (מהסוף להתחלה)

קיבלנו מערך ממוין.

פסודו קוד

פונקציות עזר:

Build-Heap(A)
heap_size[A] <- length[A]
for i <- length[A]/2 Downto 1

do Heapify(A,i)

(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)

הפונקציה העיקרית:

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)

סיבוכיות זמן ריצה

O(nlog(n))