אלגוריתמיקה ומבני נתונים

תכנות, אלגוריתמיקה ו-Web · 4–5 שעות

⌨ כתיבת קוד (3)תרגילים ומשימות קוד לשיעור 9

// סקירה

אלגוריתמיקה ומבני נתונים — Stack, Queue, חיפוש ומיון

Python מסתירה הרבה מורכבות מאחורי list ו-dict. אבל בגאמא — שואלים ישירות: "מה הסיבוכיות של push ל-stack?" "למה Binary Search הוא O(log n)?". זה השיעור שעונה על הכל.

✓נושאי השיעור

Big-O Notation — O(1), O(log n), O(n), O(n log n), O(n²) — ניתוח קוד
Stack (LIFO) — push/pop O(1), סוגריים מאוזנים, Undo/Redo
Queue (FIFO) — enqueue/dequeue O(1) עם deque, תורים, BFS
Deque — שני קצוות, maxlen, Sliding Window
Linked List — Node+next, הוספה לתחילה O(1), גישה O(n)
Binary Search — O(log n), דורש רשימה ממוינת
Bubble / Merge / Quick Sort — השוואת סיבוכיויות
Recursion — Base Case + Recursive Case + Memoization
Backtracking — נסה-חזור, Pruning לאופטימיזציה

🎯 קשר למיון גאמא

שאלון: "מה סיבוכיות dict.get()? מה ההבדל בין Stack לQueue?" כנס מבחנים: שאלות Dry-Run על לולאות מקוננות — Big-O ניתוח. שיעורים 11–14 (שפה מומצאת): הבנת לולאות תלויה בידע זה.

// פרק 1

Big-O Notation: מדידת יעילות

Big-O מודד כמה פעולות נדרשות ביחס לגודל הקלט n. לא שניות — מחשבים שונים מהירים שונה. Big-O שומר רק את האיבר הדומיננטי ומוריד קבועים.

Big-O	שם	דוגמה	לn=1000
O(1)	Constant	dict[key], Stack push/pop	1 פעולה
O(log n)	Logarithmic	Binary Search	10 פעולות
O(n)	Linear	Linear Search, list scan	1,000
O(n log n)	Linearithmic	Merge Sort, Quick Sort avg	~10,000
O(n²)	Quadratic	Bubble Sort, nested loops	1,000,000
O(2ⁿ)	Exponential	Recursive Fibonacci naive	10^301!

# O(1) — לא תלוי ב-n
def get_first(lst): return lst[0]

# O(n) — לולאה אחת
def find_max(lst):
    max_val = lst[0]
    for x in lst:        # ← n פעמים
        if x > max_val: max_val = x
    return max_val

# O(n²) — לולאה בתוך לולאה
def has_duplicate(lst):
    for i in range(len(lst)):       # ← n פעמים
        for j in range(i+1, len(lst)):  # ← עד n פעמים
            if lst[i] == lst[j]: return True
    return False

# O(log n) — חצייה בכל שלב (Binary Search)
# n=1,000,000: לוקח מקסימום 20 שלבים! log₂(1,000,000) ≈ 20

💡 כלל ה-Dominant Term

f(n) = 3n² + 5n + 100 → O(n²). Big-O שומר רק האיבר הגדול ביותר ומוריד קבועים.
f(n) = n·log(n) + n → O(n log n). f(n) = 1000 → O(1).

✏תרגול עצמי3 שאלות

שאלה 1.1

מה הסיבוכיות של: for i in range(n): for j in range(n): pass

✓ תשובה: ד) O(n²) — לולאה בתוך לולאה: n × n = n² פעולות. כלל אצבע: k לולאות מקוננות = O(nᵏ).

שאלה 1.2

מה ה-Dominant Term של f(n) = 3n² + 100n + 5000?

✓ תשובה: ד) O(n²) — Big-O מוריד מקדמים קבועים: O(3n²) = O(n²). n² גדול מ-n לכל n גדול. הביטוי הדומיננטי קובע.

שאלה 1.3

כמה שלבים מקסימום ידרוש Binary Search על n=1,000,000?

✓ תשובה: ג) כ-20 — log₂(1,000,000) ≈ 20. Binary Search O(log n): כל שלב מחצה את מרחב החיפוש. זו כוחה של סיבוכיות לוגריתמית!

🎯 דגש למבחן

ב-Big-O מתעלמים מקבועים ומאיברים מסדר גודל קטן יותר. Big-O מתאר קצב גדילה כש-n שואף לאינסוף, ולכן f(n) = 3n² + 100n + 5000 הוא פשוט O(n²): כבר ב-n = 1000 האיבר הריבועי הוא 3,000,000 מול 105,000 של כל השאר — האיברים הקטנים נבלעים. הכלל: שומרים רק את האיבר הדומיננטי ומוחקים את המקדם. גם O(2n) הוא O(n) ו-O(n² + n log n) הוא O(n²). שימו לב לפעולות עוקבות מול מקוננות: לולאה אחרי לולאה = O(n + n) = O(n), אבל לולאה בתוך לולאה = O(n²).

// פרקים 2–3

Stack (LIFO) ו-Queue (FIFO)

Stack = אחרון נכנס ראשון יוצא (ערימת צלחות). Queue = ראשון נכנס ראשון יוצא (תור בסופר). שתיהן עם כל ה-operations ב-O(1).

Stack — מימוש ויישומים

class Stack:
    def __init__(self): self._data = []
    def push(self, item): self._data.append(item)    # O(1)
    def pop(self):                                     # O(1)
        if self.is_empty(): raise IndexError("Stack ריק!")
        return self._data.pop()
    def peek(self):                                    # O(1)
        if self.is_empty(): raise IndexError("Stack ריק!")
        return self._data[-1]
    def is_empty(self): return len(self._data) == 0
    def __len__(self): return len(self._data)
    def __str__(self): return f"Stack({self._data})"

# יישום: בדיקת סוגריים מאוזנים
def is_balanced(expression: str) -> bool:
    stack = Stack()
    pairs = {')':'(', ']':'[', '}':'{'}
    for char in expression:
        if char in '([{':
            stack.push(char)
        elif char in ')]}':
            if stack.is_empty(): return False
            if stack.pop() != pairs[char]: return False
    return stack.is_empty()

print(is_balanced("(a+b)*[c-d]"))   # True
print(is_balanced("(a+b]"))         # False

Queue — מימוש עם deque

from collections import deque  # תמיד deque לQueue, לא list!

class Queue:
    def __init__(self): self._data = deque()
    def enqueue(self, item): self._data.append(item)     # O(1)
    def dequeue(self):                                    # O(1)!
        if self.is_empty(): raise IndexError("Queue ריק!")
        return self._data.popleft()   # ← O(1) עם deque!
    def peek(self):
        if self.is_empty(): raise IndexError("Queue ריק!")
        return self._data[0]
    def is_empty(self): return len(self._data) == 0
    def __len__(self): return len(self._data)

q = Queue()
q.enqueue("Alice"); q.enqueue("Bob"); q.enqueue("Carol")
print(q.dequeue())  # Alice — הראשונה שנכנסה!

! למה לא list כ-Queue? ›

list.pop(0) = O(n)! Python צריכה להזיז כל שאר האיברים שמאלה. deque.popleft() = O(1). תמיד השתמש ב-deque לQueue.

הרחבה Deque — שני קצוות ו-Sliding Window ›

from collections import deque

d = deque([1, 2, 3])
d.append(4)        # הוסף ימין: [1,2,3,4]
d.appendleft(0)    # הוסף שמאל: [0,1,2,3,4]
d.pop()            # הסר ימין → 4
d.popleft()        # הסר שמאל → 0

# Sliding Window — maxlen!
d = deque(maxlen=3)
for i in range(6):
    d.append(i)
    print(list(d))
# [0] → [0,1] → [0,1,2] → [1,2,3] → [2,3,4] → [3,4,5]

מבנה	הכנסה	הוצאה	גישה אקראית	מתאים ל
Stack	O(1) למעלה	O(1) מלמעלה	O(n)	Undo, DFS, recursion
Queue	O(1) לסוף	O(1) מהתחלה	O(n)	תורים, BFS, scheduling
Deque	O(1) שני צדדים	O(1) שני צדדים	O(n)	Sliding window
List	O(1) לסוף	O(n) מהתחלה	O(1)	Random access
Dict/Set	O(1)	O(1)	O(1)	Key-value lookup

✏תרגול עצמי3 שאלות

שאלה 2.1

מה ההבדל בין LIFO לבין FIFO?

✓ תשובה: ג) — LIFO = Last In First Out = Stack (ערימת צלחות: אחרון שנשם, ראשון שנלקח). FIFO = First In First Out = Queue (תור: ראשון שהגיע, ראשון שמשולם).

שאלה 2.2

from collections import deque
d = deque(maxlen=3)
for i in range(5):
    d.append(i)
print(list(d))

מה הפלט?

✓ תשובה: ג) [2,3,4] — maxlen=3: כשנוסף איבר 4 (ה-5), איבר 1 (ה-2) נדחף החוצה. אחרי 5 הוספות: נשארים 3 האחרונים [2,3,4].

שאלה 2.3

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop()
print(stack)

מה הפלט?

✓ תשובה: א) [1,2] — list כStack: append=push לסוף, pop()=pop מסוף. append(1,2,3)=[1,2,3]. pop() מסיר 3 (האחרון) → [1,2].

🎯 דגש למבחן

Deque: קצוות ב-O(1), אמצע ב-O(n). collections.deque ממומש כרשימה מקושרת של בלוקים, ולכן append, appendleft, pop ו-popleft כולם O(1) — ולכן הוא הכלי הנכון ל-Queue (בעוד list.pop(0) הוא O(n) כי כל האיברים מוסטים). אבל גישה אקראית לאמצע היא O(n): d[500] מחייב מעבר על הבלוקים, בשונה מ-list שבה lst[500] הוא O(1). הכלל לבחירה: הרבה הוספות/הסרות מהקצוות → deque; הרבה גישות לפי אינדקס → list.

// פרק 5

Binary Search: חיפוש דיכוטומי O(log n)

חיפוש ברשימה ממוינת על ידי חצייה חוזרת. בכל שלב מחצים את מרחב החיפוש. דרישה קריטית: הרשימה חייבת להיות ממוינת!

⚙️ האלגוריתם

lo = 0, hi = n-1. בכל שלב: mid = (lo+hi)//2.
• אם lst[mid] == target → מצאנו!
• אם lst[mid] < target → lo = mid+1 (חפש ימין)
• אם lst[mid] > target → hi = mid-1 (חפש שמאל)
• אם lo > hi → לא נמצא → return -1

def binary_search(lst: list, target) -> int:
    """מחזיר אינדקס של target, -1 אם לא נמצא. O(log n)"""
    lo, hi = 0, len(lst) - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        if lst[mid] == target:
            return mid              # מצאנו!
        elif lst[mid] < target:
            lo = mid + 1            # חפש בחצי ימני
        else:
            hi = mid - 1            # חפש בחצי שמאלי
    return -1                       # לא נמצא

# דוגמה מפורטת:
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
# שלב 1: lo=0, hi=9, mid=4 → arr[4]=9  < 11 → lo=5
# שלב 2: lo=5, hi=9, mid=7 → arr[7]=15 > 11 → hi=6
# שלב 3: lo=5, hi=6, mid=5 → arr[5]=11 == 11 → return 5!

print(binary_search(arr, 11))  # 5
print(binary_search(arr, 6))   # -1 (לא קיים)

✏תרגול עצמי3 שאלות

שאלה 5.1

מה הדרישה הקריטית של Binary Search?

✓ תשובה: ד) — ללא מיון, ההחלטה "חפש ימין/שמאל" שגויה. Binary Search מבוסס כולו על ההנחה שאם lst[mid] < target, target חייב להיות בחצי הימני.

שאלה 5.2

כמה שלבים Binary Search ידרוש לn=64?

✓ תשובה: א) 6 — log₂(64) = 6. כי 2⁶ = 64. כל שלב מחצה: 64→32→16→8→4→2→1 = 6 חצייות מקסימום.

שאלה 5.3

מה יחזיר binary_search([1,3,5,7,9], 6)?

✓ תשובה: ד) -1 — 6 לא קיים ברשימה. lo=0,hi=4 → mid=2,val=5<6 → lo=3 → mid=3,val=7>6 → hi=2 → lo(3)>hi(2) → return -1.

// פרק 6

אלגוריתמי מיון

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

אלגוריתם	Best	Average	Worst	Space	יציב?
Bubble	O(n)	O(n²)	O(n²)	O(1)	כן
Insertion	O(n)	O(n²)	O(n²)	O(1)	כן
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	כן
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	לא
Python .sort()	—	O(n log n)	O(n log n)	O(n)	כן (Timsort)

Bubble Sort — O(n²)

def bubble_sort(lst):
    n = len(lst)
    lst = lst.copy()
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                swapped = True
        if not swapped: break  # אופטימיזציה: כבר ממוין
    return lst

arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))  # [11, 12, 22, 25, 34, 64, 90]

Merge Sort — O(n log n) תמיד

def merge_sort(lst):
    if len(lst) <= 1: return lst
    mid = len(lst) // 2
    left  = merge_sort(lst[:mid])    # Divide ← רקורסיה!
    right = merge_sort(lst[mid:])    # Divide ← רקורסיה!
    return merge(left, right)        # Combine

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])   # שאריות שמאל
    result.extend(right[j:])  # שאריות ימין
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]

הרחבה Quick Sort ו-Memoization ›

def quick_sort(lst):
    if len(lst) <= 1: return lst
    pivot = lst[len(lst)//2]
    left   = [x for x in lst if x < pivot]
    middle = [x for x in lst if x == pivot]
    right  = [x for x in lst if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))  # [1, 1, 2, 3, 6, 8, 10]
# Worst Case O(n²): pivot תמיד קיצוני (רשימה ממוינת + pivot ראשון)

# Memoization — Fibonacci מO(2ⁿ) לO(n)
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(10))   # 55 (מהיר!)

✏תרגול עצמי3 שאלות

שאלה 6.1

מה הסיבוכיות של Merge Sort בכל מקרה (best/average/worst)?

✓ תשובה: ג) O(n log n) תמיד — Merge Sort תמיד מחלק לשניים (log n רמות) ומוזג O(n) בכל רמה = O(n log n) בכל מקרה. לכן מועדף כשWorst Case קריטי.

שאלה 6.2

מה Quick Sort Worst Case ומתי הוא קורה?

✓ תשובה: א) O(n²) — כשpivot תמיד קיצוני (אפס/אחד איבר בצד אחד): n + (n-1) + ... = O(n²). פתרון: pivot אקראי או מהאמצע.

שאלה 6.3

מה Python's .sort() מממשת?

✓ תשובה: א) Timsort — Python's .sort() ו-sorted() משתמשות ב-Timsort. היברידי של Merge Sort ו-Insertion Sort. O(n log n) worst case, stable, מותאם לreal-world data.

🎯 דגש למבחן

יציבות (Stability) — מה זה ולמה זה חשוב. מיון הוא יציב אם שני איברים בעלי אותו מפתח שומרים על הסדר היחסי המקורי ביניהם. דוגמה: ברשימת עובדים הממוינת לפי שם, מיון נוסף לפי מחלקה במיון יציב ישאיר בכל מחלקה את השמות לפי סדר האלפבית — כך בונים מיון רב-שלבי. Merge Sort יציב, Quick Sort וה-Heap Sort אינם יציבים. בפייתון sorted() ו-list.sort() מממשים Timsort (הכלאה של Merge ו-Insertion) והם תמיד יציבים — O(n log n) בממוצע ובמקרה הגרוע, ו-O(n) על נתונים כמעט ממוינים.

// פרק 7

Recursion ו-Backtracking

Recursion = פונקציה שקוראת לעצמה. חייבת: Base Case (עצירה), Recursive Case (קריאה עצמית), Progress (כל קריאה מתקרבת לBase Case).

# פקטוריאל — n!
def factorial(n: int) -> int:
    if n <= 1: return 1          # Base Case
    return n * factorial(n - 1) # Recursive Case

# factorial(4) = 4 * factorial(3) = 4*3*2*1 = 24

# Fibonacci — 3 גישות
# Naive — O(2ⁿ) ← מאוד איטי!
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n-1) + fib_naive(n-2)

# Memoization — O(n) ← מהיר!
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Dynamic Programming — O(n), O(1) space ← הכי טוב!
def fib_dp(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b

print(fib_dp(10))   # 55

! אין Base Case → RecursionError ›

def bad(n):
    return n + bad(n-1)   # אין Base Case!
# RecursionError: maximum recursion depth exceeded
# = Stack Overflow: כל קריאה מוסיפה Frame ל-Call Stack עד שנגמר

# Python מוגבל ל-1000 frames. sys.setrecursionlimit() לא פתרון אמיתי.

✏תרגול עצמי3 שאלות

שאלה 7.1

מה Base Case ברקורסיה? מה יקרה בלי Base Case?

✓ תשובה: ב) — Base Case = תנאי עצירה שמחזיר ערך ישירות (ללא קריאה עצמית). בלי Base Case → קריאות אינסופיות → RecursionError (הרעיון: Call Stack מתמלא).

שאלה 7.2

def f(n): if n<=0: return 0; return n + f(n-1) — מה יחזיר f(5)?

✓ תשובה: ד) 15 — f(5)=5+f(4)=5+4+f(3)=5+4+3+f(2)=5+4+3+2+f(1)=5+4+3+2+1+f(0)=5+4+3+2+1+0=15.

שאלה 7.3

מה Memoization? כיצד היא משפרת Fibonacci?

✓ תשובה: א) — Memoization: שמור תוצאת f(n) ב-dict. בפעם הבאה — תחזיר מהdict. fib_naive(50) לוקח שעות. fib_memo(50) = מיידי. כל תוצאה מחושבת פעם אחת בלבד.

// אתגר מעשי

אתגר מעשי — אלגוריתמיקה ומבני נתונים

שיא השיעור: לבנות, לתקן ולנתח — לא לזהות תשובה. פתרו את משימת החובה ואז את האתגר שמעליה; ההגשה נבדקת אוטומטית מול מקרי-קצה נסתרים (וחלקן אוכפות יעילות דרך גודל-קלט).

T2 · בסיסי200 נק'~15 דק'algorithmic

זוג שמסתכם ליעד

נתונה רשימת מספרים שלמים ומספר יעד. החזר True אם קיימים שני איברים *שונים במיקומם* שסכומם שווה ליעד, אחרת False. (זו דוגמת-הזהב A — משמשת כמשימת החימום של שיעור האלגוריתמיקה.)

דוגמאות

has_pair_sum([1,2,3], 5) → True

has_pair_sum([1,2,3], 7) → False

has_pair_sum([3,3], 6) → True

הפתרון שלךהפתרון נשמר מקומית ומשותף עם עמוד „כתיבת קוד”.

פתרון-ייחוס זוג שמסתכם ליעד ›

def has_pair_sum(nums, target):
    seen = set()
    for n in nums:
        if target - n in seen:
            return True
        seen.add(n)
    return False

T3 · בינוני350 נק'~20 דק'algorithmic

קבוצת החזקה (Subsets)

נתונה רשימת מספרים ייחודיים nums. החזר את כל תת-הקבוצות שלה (קבוצת החזקה) לפי הסדר הקנוני: מתחילים מהקבוצה הריקה, ובכל צעד מוסיפים את האיבר הבא לכל תת-הקבוצות שנצברו עד כה. לדוגמה [1,2] → [[], [1], [2], [1,2]].

דוגמאות

subsets([]) → [[]]

subsets([1]) → [[], [1]]

subsets([1,2]) → [[], [1], [2], [1,2]]

הפתרון שלךהפתרון נשמר מקומית ומשותף עם עמוד „כתיבת קוד”.

פתרון-ייחוס קבוצת החזקה (Subsets) ›

def subsets(nums):
    res = [[]]
    for n in nums:
        res = res + [cur + [n] for cur in res]  # מכפיל את קבוצת-החזקה בכל צעד
    return res

T3 · בינוני400 נק'~25 דק'algorithmic

ספירת מופעים במערך ממוין (Binary Search)

נתון מערך ממוין (לא יורד) arr ורשימת שאילתות queries. עבור כל שאילתה q החזר כמה פעמים q מופיע ב-arr, כרשימת תשובות באותו סדר. חובה O(log n) לשאילתה (חיפוש בינארי לגבול שמאלי וימני): קלט של מיליון איברים ועשרות אלפי שאילתות חייב לרוץ בזמן. סריקה לינארית לכל שאילתה (O(n·q)) תיפסל ב-timeout.

דוגמאות

count_occurrences([1,2,2,2,3], [2]) → [3]

count_occurrences([1,2,2,2,3], [4]) → [0]

count_occurrences([1,1,1], [1,2]) → [3, 0]

הפתרון שלךהפתרון נשמר מקומית ומשותף עם עמוד „כתיבת קוד”.

פתרון-ייחוס ספירת מופעים במערך ממוין (Binary Search) ›

import bisect
def count_occurrences(arr, queries):
    return [bisect.bisect_right(arr, q) - bisect.bisect_left(arr, q)
            for q in queries]              # O(log n) לכל שאילתה

// סיכום

סיכום השיעור

✓מה למדנו בשיעור זה

Big-O: O(1) O(log n) O(n) O(n log n) O(n²) — ניתוח כמות פעולות לפי גודל קלט
Stack (LIFO): push/pop O(1), יישומים: סוגריים, Undo/Redo, DFS
Queue (FIFO): enqueue/dequeue O(1) עם deque, תורים, BFS
Deque: שני קצוות, maxlen, Sliding Window
Linked List: Node+next, O(1) להוספה בתחילה, O(n) לגישה אקראית
Binary Search: O(log n), דורש רשימה ממוינת
Bubble O(n²), Merge O(n log n) תמיד, Quick O(n log n) avg / O(n²) worst
Recursion: Base Case + Recursive Case, Memoization
Backtracking: נסה-חזור, Pruning לאופטימיזציה

🎯 השיעור הבא

שיעור 10 — פרויקט אישי
מומלץ: ממש את כל מבני הנתונים ב-Python מהראש. Binary Search, Stack, Queue — כבר בשיעור 11.

✏תרגול סיום — גאמא סגנון3 שאלות

גאמא סגנון א׳

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
print([fib(i) for i in range(7)])

מה הפלט?

✓ תשובה: ד) [0,1,1,2,3,5,8] — סדרת פיבונאצ'י. fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8. range(7) = 0 עד 6 → 7 ערכים.

גאמא סגנון ב׳

מה ההבדל בין Merge Sort לבין Quick Sort? מה היתרון של כל אחד?

✓ תשובה: ב) — Merge: stable, guaranteed O(n log n), O(n) memory. Quick: בפועל מהיר יותר (cache-friendly), O(log n) space, אבל O(n²) worst. Python = Timsort (hybrid).

גאמא סגנון ג׳

מה הסיבוכיות של חיפוש ב-set ב-Python?

✓ תשובה: ב) O(1) amortized — set ב-Python מיושמת כ-hash table. חיפוש (x in s) = O(1) amortized. לעומת list שחיפוש = O(n). לכן for x in big_list: if x in my_set: עדיף ל-if x in my_list.

שאלות תרגול ותשובות (10)

שאלה 1 · מהי סיבוכיות הזמן של הקוד הבא?

for i in range(n):
    for j in range(n):
        pass

א. O(1)
ב. O(n)
ג. O(n log n)
ד. O(n²)

תשובה: ד

שתי לולאות מקוננות על n — n·n פעולות.

שאלה 2 · מהי הסיבוכיות של f(n) = 3n² + 100n + 5000?

א. O(n)
ב. O(n²)
ג. O(3n²)
ד. O(n² + n)

תשובה: ב

מוחקים מקדמים ואיברים מסדר גודל קטן יותר — נשאר האיבר הדומיננטי בלבד.

שאלה 3 · כמה שלבים לכל היותר יידרשו ל-Binary Search על מערך ממוין בגודל 1,000,000?

א. 1,000
ב. ~20
ג. 500,000
ד. 1,000,000

תשובה: ב

log₂(1,000,000) ≈ 20 — כל שלב חוצה את טווח החיפוש.

שאלה 4 · מה יודפס?

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.pop()
print(stack[-1])

א. 2
ב. 3
ג. 1
ד. שגיאה

תשובה: א

LIFO: pop מסיר את 3, ולכן העליון בערימה הוא 2.

שאלה 5 · מה יודפס?

from collections import deque

d = deque(maxlen=3)
for i in range(5):
    d.append(i)
print(list(d))

א. [0, 1, 2]
ב. [0, 1, 2, 3, 4]
ג. [2, 3, 4]
ד. [4, 3, 2]

תשובה: ג

maxlen=3 — כל הוספה מעבר לגבול דוחקת אוטומטית את האיבר משמאל.

שאלה 6 · מהי סיבוכיות הגישה לאיבר באמצע deque, למשל d[500]?

from collections import deque

d = deque(range(1000))
x = d[500]   # ?
d.appendleft(-1)  # O(1)

א. O(1)
ב. O(n)
ג. O(log n)
ד. O(n log n)

תשובה: ב

הקצוות ב-deque הם O(1), אבל גישה אקראית לאמצע דורשת מעבר — O(n). ב-list זה הפוך.

שאלה 7 · מה התנאי ההכרחי כדי להריץ Binary Search?

א. הרשימה חייבת להיות ממוינת
ב. הרשימה חייבת להכיל מספרים בלבד
ג. אורך הרשימה חייב להיות חזקה של 2
ד. הרשימה חייבת להיות deque

תשובה: א

על רשימה לא ממוינת האלגוריתם ייתן תשובה שגויה בלי לזרוק שגיאה.

שאלה 8 · מה משמעות המונח "מיון יציב" (Stable Sort)?

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

תשובה: ב

יציבות מאפשרת מיון רב-שלבי — מיון לפי מחלקה משמר את סדר השמות הקודם.

שאלה 9 · איזה אלגוריתם מיון מממשות sorted() ו-list.sort() בפייתון, ומה סיבוכיותו במקרה הגרוע?

nums = [5, 2, 9, 1, 5, 6]
nums.sort()      # ?
print(nums)

א. Timsort, O(n log n)
ב. Quick Sort, O(n²)
ג. Bubble Sort, O(n²)
ד. Heap Sort, O(n log n)

תשובה: א

Timsort הוא הכלאה של Merge ו-Insertion — יציב, O(n log n) במקרה הגרוע ו-O(n) על נתונים כמעט ממוינים.

שאלה 10 · מה יחזיר הקוד?

def f(n):
    if n <= 0:
        return 0
    return n + f(n - 1)

print(f(5))

א. 5
ב. 10
ג. 12
ד. 15

תשובה: ד

5+4+3+2+1 = 15; תנאי העצירה (Base Case) הוא n <= 0.

← שיעור קודם שיעור הבא →