1. השלמות מהרצאה קודמת
Little-o (חסם עליון לא הדוק)
\(f(n) \in o(g(n))\) אם לכל קבוע \(c > 0\) קיים \(n_0\) כך שלכל \(n > n_0\), \(f(n) < c \cdot g(n)\). שקול: \(\lim_{n \to \infty} f(n)/g(n) = 0\).
דוגמאות: \(2n = o(n^2)\), \(\log n = o(n)\). אבל \(n \notin o(2n)\) (הגבול הוא 1/2).
Little-ω (חסם תחתון לא הדוק)
\(f(n) \in \omega(g(n))\) אם לכל \(c > 0\), קיים \(n_0\) כך שלכל \(n > n_0\), \(f(n) > c \cdot g(n)\). שקול: \(\lim f/g = \infty\).
דוגמאות: \(n \log n = \omega(n)\), \(2^{0.001n} = \omega(n^{300})\).
| סימון | משמעות |
|---|
| \(O, o\) | חסם עליון (הדוק / לא הדוק) |
| \(\Omega, \omega\) | חסם תחתון (הדוק / לא הדוק) |
| \(\Theta\) | חסם הדוק משני הצדדים |
2. בעיית המיון
הגדרה
קלט: סדרת \(n\) אובייקטים \(\langle a_1, a_2, \ldots, a_n \rangle\) עם יחס סדר \(\leq\) מוגדר עליהם.
פלט: פרמוטציה \(\langle b_1, b_2, \ldots, b_n \rangle\) המקיימת \(b_1 \leq b_2 \leq \ldots \leq b_n\).
למה ממיינים?
- Binary Search ב-\(\Theta(\log n)\) במקום \(O(n)\).
- גישה ב-\(O(1)\) לאיבר ה-\(k\) בגודלו.
- זיהוי כפולים בקלות.
3. קריטריוני הערכה
זמן
- חסם תחתון טריוויאלי: \(\Omega(n)\) (חייבים לקרוא כל איבר).
- חסם עליון פשוט: \(O(n^2)\) (Bubble Sort, Insertion).
- השאלה הגדולה: ניתן לסגור את הפער? כן: \(\Theta(n \log n)\) השג.
מקום
- In-place: \(O(1)\) מקום עזר. לא צריך העתקה.
- שלא in-place: \(O(n)\) מקום עזר.
- ביניים: \(O(\log n)\) למחסנית רקורסיה.
יציבות (Stability)
הגדרה
אלגוריתם מיון
יציב אם הוא לא משנה את הסדר היחסי של מפתחות שווים.
דוגמה
קלט: \(5_a, 8, 3_a, 5_b, 4, 3_b, 2, 3_c\) (אינדקסים מציינים סדר מקורי).
- יציב: \(2, 3_a, 3_b, 3_c, 4, 5_a, 5_b, 8\) ✓
- לא יציב: \(2, 3_c, 3_b, 3_a, 4, 5_a, 5_b, 8\) ✗
למה זה חשוב? במסדי נתונים: מיון לפי שם ואז לפי מדינה — האם השמות בכל מדינה עדיין ממוינים? רק במיון יציב.
Bubble Sort (השוואה)
| זמן | מקום | יציב |
|---|
| Worst \(\Theta(n^2)\), Best \(\Theta(n)\), Avg \(\Theta(n^2)\) | in-place | כן |
4. HeapSort
הרעיון
משתמשים ב-
Max-Heap. בכל סיבוב מבצעים DeleteMax ושמים את המקסימום בסוף המערך.
HeapSort(A):
BuildMaxHeap(A) // O(n)
n ← length(A)
for s = n downto 2:
x ← A[1] // המקסימום הנוכחי
PercDown(1, A[s], s−1, A) // הזזת האחרון לראש + תיקון
A[s] ← x // המקסימום נשמר ב-A[s]
אינווריאנטים
• \(A[s+1..n]\) ממוין בסדר עולה.
• \(A[1..s]\) מהווה Max-Heap חוקי.
סיבוכיות
ניתוח
- BuildMaxHeap: \(O(n)\)
- \(n-1\) פעמים DeleteMax: כל אחת \(O(\log s) \leq O(\log n)\) ⟹ \(O(n \log n)\)
- Worst case: \(\Theta(n \log n)\) (חסם תחתון: קלט ממוין מהגדול לקטן).
- Best case: \(\Theta(n)\) (כל האיברים זהים), אחרת \(\Theta(n \log n)\).
- Average: \(\Theta(n \log n)\).
| זמן Worst | זמן Best | מקום | יציב |
|---|
| \(\Theta(n \log n)\) | \(\Theta(n)\) | in-place | לא |
5. MergeSort - Divide and Conquer
אסטרטגיה
•
Divide: חלק את הסדרה לשתי תת-סדרות בגודל \(n/2\).
•
Conquer: מיין רקורסיבית.
•
Combine: מזג את שתי התת-סדרות הממוינות.
•
בסיס: סדרה באורך 1 כבר ממוינת.
Mergesort(A, p, r):
if p < r:
q ← ⌊(p+r)/2⌋
Mergesort(A, p, q)
Mergesort(A, q+1, r)
Merge(A, p, q, r)
Merge(A, p, q, r):
L ← A[p..q]; R ← A[q+1..r]
i ← 1; j ← 1
for k = p to r:
if L[i] ≤ R[j]:
A[k] ← L[i]; i++
else:
A[k] ← R[j]; j++
// (sentinel ∞ בקצוות עוזר במימוש)
Merge ב-\(\Theta(n)\)
לולאה אחת על \(r-p+1\) איברים, השוואה והכנסה \(O(1)\) לכל אחד.
ניתוח סיבוכיות
משוואה
\(T(n) \leq 2 T(n/2) + c_1 \cdot n\), \(T(1) \leq c_2\).
שיטת ההצבה (אם \(n = 2^k\)):
\(T(n) \leq 2T(n/2) + c_1 n \leq 4T(n/4) + 2c_1 n \leq \ldots \leq 2^k T(1) + k c_1 n \leq bn + c_1 n \log n = O(n \log n)\)
הוכחה באינדוקציה: נוכיח \(T(2^k) \leq d \cdot 2^k \log 2^k\) עם \(d = \max(c_1, c_2)\).
- בסיס \(k=1\): \(T(2) = c_2 \leq d \cdot 2 \cdot 1\). ✓
- צעד: \(T(2^{k+1}) \leq 2T(2^k) + c_1 \cdot 2^{k+1} \leq 2d \cdot 2^k k + d \cdot 2^{k+1} = d \cdot 2^{k+1}(k+1)\). ✓
שיטת עץ הרקורסיה (אינטואיטיבית)
עומק העץ: \(\log n\). עלות בכל רמה: \(\Theta(n)\) (סכום ה-Merges). סה"כ: \(\Theta(n \log n)\).
תכונות נוספות
| זמן (Worst, Best, Avg) | מקום | יציב |
|---|
| \(\Theta(n \log n)\) | \(\Theta(n)\) (לא in-place) | כן (אם נותנים עדיפות לאינדקס נמוך ב-Merge בשוויון) |
6. QuickSort
הרעיון
•
Divide: בחר
pivot, חלק את המערך ל-\(S_1\) (איברים \(\leq\) pivot) ו-\(S_2\) (\(>\) pivot).
•
Conquer: מיין רקורסיבית כל תת-מערך.
•
Combine: שום דבר! המערך כבר ממוין במקום.
Quicksort(A, p, r):
if r − p > 0:
q ← Partition(A, p, r)
Quicksort(A, p, q−1)
Quicksort(A, q+1, r)
Partition(A, p, r):
x ← A[r]; j ← r; i ← p−1
while true:
repeat j ← j−1 until A[j] ≤ x or j < p
repeat i ← i+1 until A[i] > x or i > r
if i < j: swap A[i] ↔ A[j]
else: swap A[j+1] ↔ A[r]
return j+1
ניתוח
משוואת הזמן
\(T(0) = O(1)\). אם \(p\) הוא מיקום ה-pivot אחרי Partition: \(T(n) = \Theta(n) + T(p-1) + T(n-p-1)\).
Best Case - \(\Theta(n \log n)\)
ה-pivot מחלק לחלקים שווים (חציון). \(T(n) = 2T(n/2) + \Theta(n)\) — בדיוק כמו MergeSort. עומק \(\log n\), עבודה \(\Theta(n)\) בכל רמה.
Worst Case - \(\Theta(n^2)\)
ה-pivot גרוע ביותר — מחלק ל-0 ו-(n-1). קורה למשל למערך כבר ממוין כשבוחרים את האחרון.
\(T(n) = T(n-1) + cn = c(n + (n-1) + \ldots + 2) = \Theta(n^2)\)
Average Case - \(\Theta(n \log n)\)
אינטואיציה: אם בכל רמה ה-pivot מחלק ביחס קבוע \(c < 1\) (למשל 9/10), עומק הרקורסיה הוא \(\log_{1/c} n = O(\log n)\). מסקנה: \(\Theta(n \log n)\).
ניתוח פורמלי: בהנחה שכל פוזיציית pivot שקולה (הסתברות \(1/n\)):
\(T_{\text{avg}}(n) = dn + \dfrac{2}{n} \sum_{k=1}^{n} T_{\text{avg}}(k-1)\)
אחרי טריקים אלגבריים מגיעים ל-\(T_{\text{avg}}(n)/(n+1) = O(\log n)\) ⟹ \(T_{\text{avg}}(n) = O(n \log n)\), כי \(H_n = \sum 1/k = \Theta(\log n)\).
בחירת ה-Pivot
- הראשון/האחרון: פשוט, אבל יוצר Worst על מערך ממוין.
- חציון של 3 (שמאל, אמצע, ימין): פתרון טוב, מקטין סיכוי ל-Worst.
- אקראי: תוחלת \(O(n \log n)\) ללא תלות בקלט.
| זמן Best/Avg | זמן Worst | מקום | יציב |
|---|
| \(\Theta(n \log n)\) | \(\Theta(n^2)\) | in-place + \(O(\log n)\) מחסנית בממוצע | לא |