1. מהו אלגוריתם ומהו מבנה נתונים
הגדרה: Data (נתונים)
מידע (Information) שניתן לנתח ולעבד — מספרים, מילים, שירים, סרטים וכו'.
הגדרה: Algorithm (אלגוריתם)
פרוצדורה מוגדרת-היטב לפתרון בעיה.
Input → עיבוד (manipulation) →
Output
הגדרה: Data Structure (מבנה נתונים)
הדרך שבה הנתונים מאורגנים.
מבנה נתונים = אחסון נתונים + אלגוריתמים לפעולות עליהם.
2. בעיית המיון (Sorting Problem)
הגדרת הבעיה
Input: סדרה \(\langle a_1, a_2, \ldots, a_n \rangle\)
Output: תמורה \(\langle b_1, b_2, \ldots, b_n \rangle\) כך ש-\(b_1 \leq b_2 \leq \ldots \leq b_n\)
דוגמה
Input: \(\langle 31, 41, 59, 26, 41, 58 \rangle\) → Output: \(\langle 26, 31, 41, 41, 58, 59 \rangle\)
הערה
ניתן למיין לא רק מספרים — גם תמונות, שירים, סרטים, שמות. צריך להגדיר/לציין סדר (order).
3. Insertion Sort — פסאודו-קוד
עוברים על האיברים לפי סדר. עבור כל איבר — מכניסים אותו למקום הנכון בתוך הקידומת שכבר ממוינת, עד שהאיבר האחרון מוכנס.
פסאודו-קוד: Insertion-Sort(A)
for i ← 2 to length[A]
key ← A[i]
j ← i - 1
while j > 0 and A[j] > key
A[j+1] ← A[j]
j ← j - 1
end
A[j+1] ← key
end
מעקב — דוגמה
דוגמה: מיון [5, 2, 4, 6, 1, 3]
- i=2: key=2 → [2, 5, 4, 6, 1, 3]
- i=3: key=4 → [2, 4, 5, 6, 1, 3]
- i=4: key=6 → [2, 4, 5, 6, 1, 3]
- i=5: key=1 → [1, 2, 4, 5, 6, 3]
- i=6: key=3 → [1, 2, 3, 4, 5, 6]
סיבוכיות
- Best case: \(O(n)\) — המערך כבר ממוין.
- Worst case: \(O(n^2)\) — המערך ממוין בסדר הפוך.
7. Stack, Queue, Deque ADTs
הגדרה: Stack (מחסנית) — LIFO
Push(S, b) — הכנסת איבר לראשTop(S) — החזרת האיבר בראשPop(S) — מחיקה והחזרת האיבר בראש
הכנסה ומחיקה רק מקצה אחד.
הגדרה: Queue (תור) — FIFO
Enqueue(Q, b) — הכנסת איבר לסוףHead(Q) — החזרת האיבר בראשDequeue(Q) — מחיקה והחזרת האיבר בראש
הכנסה בסוף, מחיקה מההתחלה.
הגדרה: Deque (תור דו-כיווני)
Insert-First, Insert-LastDelete-First, Delete-LastRetrieve-First, Retrieve-Last
מכליל גם Stack וגם Queue.
9. מימוש Sequence עם מערך
מבנה
struct עם שדות:
array,
maxlen (M),
length (n).
צריך לדעת את
maxlen מראש.
| פעולה |
סיבוכיות |
| Retrieve(S, i) |
\(O(1)\) |
| Insert-Last / Delete-Last |
\(O(1)\) |
| Insert(S, i, b) / Delete(S, i) |
\(O(n - i + 1)\) — צריך להזיז איברים |
פסאודו-קוד: Retrieve(S, i)
return S.array[i]
פסאודו-קוד: Insert-Last(S, b)
S.length ← S.length + 1
S.array[S.length] ← b
פסאודו-קוד: Insert(S, i, b)
for j ← S.length down to i
S.array[j+1] ← S.array[j]
end
S.array[i] ← b
S.length ← S.length + 1
10. מימוש Sequence עם מערך מעגלי (Circular Array)
הגדרה: Circular Array
מוסיפים שדה
start.
גישה:
S.array[(S.start + i) mod S.maxlen]
כעת
Insert-First ו-
Delete-First גם הם \(O(1)\) — על ידי הזזת מצביע
start.
פסאודו-קוד: Delete-First(S)
b ← S.array[S.start]
S.start ← (S.start + 1) mod S.maxlen
S.length ← S.length - 1
return b
שרשור (Concatenation)
\(O(\min\{n_1, n_2\} + 1)\) — מעתיקים את הקטן מבין השניים.
סיכום סיבוכיות — מערך מעגלי
| פעולה |
סיבוכיות |
| Insert-First / Delete-First |
\(O(1)\) |
| Insert-Last / Delete-Last |
\(O(1)\) |
| Insert(S, i, b) / Delete(S, i) |
\(O(\min\{i+1,\; n-i+1\})\) |
| Retrieve(S, i) |
\(O(1)\) |
| Concatenation |
\(O(\min\{n_1, n_2\} + 1)\) |
11. רשימה מקושרת יחידה (Singly Linked List)
הגדרה: Singly Linked List
אובייקט List עם שדות:
first,
last,
length.
כל צומת (Node):
item,
next.
אין גישה אקראית יעילה ב-\(O(1)\).
יתרונות: גודל בלתי מוגבל, אין צורך בהקצאה מראש, סריקה \(O(n)\), שרשור \(O(1)\).
פסאודו-קוד: Insert-First(L, b)
create node B
B.next ← L.first
L.first ← B
if L.length = 0: L.last ← B
L.length ← L.length + 1
סיבוכיות: \(O(1)\).
פסאודו-קוד: Retrieve-Node(L, i)
node ← L.first
for k ← 1 to i
node ← node.next
end
return node
סיבוכיות: \(O(i+1)\).
פסאודו-קוד: Insert(L, i, b)
A ← Retrieve-Node(L, i-1)
Insert-After(A, B)
סיבוכיות: \(O(i+1)\).
פסאודו-קוד: Insert-After(A, B)
B.next ← A.next
A.next ← B
סיבוכיות: \(O(1)\).
פסאודו-קוד: Delete-After(A)
A.next ← A.next.next
סיבוכיות: \(O(1)\).
מגבלה
Delete(L, i) ו-
Delete-Last דורשים \(O(n)\) ברשימה מקושרת יחידה — כי אי אפשר לחזור אחורה.
פסאודו-קוד: Concat(L1, L2)
L1.last.next ← L2.first
L1.last ← L2.last
L1.length ← L1.length + L2.length
סיבוכיות: \(O(1)\).
12. רשימה מקושרת כפולה (Doubly Linked List)
הגדרה: Doubly Linked List
כל צומת מכיל
prev וגם
next.
כעת
Insert-Last,
Delete-Last,
Delete(A) — כולם \(O(1)\).
פסאודו-קוד: Delete(A)
A.prev.next ← A.next
A.next.prev ← A.prev
סיבוכיות: \(O(1)\). שימו לב: הצומת \(A\) עצמו לא משתנה — צריך לטפל ב-L.length בנפרד.
פסאודו-קוד: Insert-After(A, B)
B.prev ← A
B.next ← A.next
A.next ← B
B.next.prev ← B
סיבוכיות: \(O(1)\).
14. מערכים דינמיים עם הכפלה (Doubling)
הרעיון
כשהמערך מלא — מקצים מערך חדש גדול יותר ומעתיקים את כל האיברים.
הגדלה ב-1 בכל פעם — יקר מדי!
עלות \(n\) פעולות Insert-Last:
\(1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2} = O(n^2)\)
אסטרטגיית הכפלה (Doubling)
כשהמערך מלא —
מכפילים את הגודל.
עלות \(n\) פעולות Insert-Last (כש-\(n = 2^k\)):
\(\underbrace{(1+1+\ldots+1)}_{n \text{ insertions}} + \underbrace{(1+2+4+\ldots+\tfrac{n}{2})}_{\text{copying}} = n + (n-1) = O(n)\)
תוצאה: Amortized cost
העלות ה-
amortized של Insert-Last עם אסטרטגיית הכפלה:
\(\frac{O(n)}{n} = O(1)\)