איך לתרגל שאלות השוואת פונקציות במבני נתונים ומבוא לאלגוריתמים?

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

כמה שאלות השוואת פונקציות יש במבני נתונים ומבוא לאלגוריתמים?

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

מה חשוב לדעת על השוואת פונקציות לקראת מבחן במבני נתונים ומבוא לאלגוריתמים?

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

מבני נתונים ומבוא לאלגוריתמים - השוואת פונקציות

סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש

סטטיסטיקות מבחנים

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

רמת קושי:

א. פתרו את נוסחת הנסיגה הבאה:

T (n) = T (n /2) + lo g n

T (1) = Θ (1)

ב. קבעו נכון/לא נכון, עם נימוק קצר:

$lo g (n!) = Θ (n lo g n)$
$n = o (n lo g n)$
$(lo g n)^{10} = o (n^{0.1})$
$\sum_{k = 0}^{l o g n} k = Θ (lo g n)$

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א

★★★★★

נוסחת נסיגהסימון אסימפטוטימשפט האבהשוואת פונקציותאסימפטוטיקה

א. נתון אלגוריתם הרץ באופן רקורסיבי. בכל שלב, האלגוריתם מבצע עבודה של

n

(לינארית בגודל הקלט), ומבצע קריאה רקורסיבית אחת לקלט בגודל

n - 2

.
1. כתבו את נוסחת הנסיגה

T (n)

.
2. פתרו את הנוסחה ומצאו חסם (

Θ

) מדויק. (שימו לב: משפט האב אינו ישים כאן ישירות).
ב. סדרו מהקטן לגדול אסימפטוטית (ייתכנו שוויונות) עם נימוק קצר:

(lo g n)^{3}, n \cdot lo g n, n / lo g n, n^{0.9}, lo g (n!)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א

★★★★★

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

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 2 T (\frac{n}{2}) + n lo g^{2} (n) if n < 100 if n \geq 100

ב) (12 נקודות) נתונות שתי פונקציות

f, g : N \to R^{+}

f (n) = 2^{l o g_{4} n}

g (n) = n^{2}

i. (6 נקודות) פרופסור אילוביץ' טענה כי השיטה הכי טובה להכריע מהו היחס האסימפטוטי בין

f (n)

ל-

g (n)

היא להחיל

lo g ()

על שתי הפונקציות, לבדוק מהו היחס האסימפטוטי בין

lo g (f (n))

ל-

lo g (g (n))

, ולטעון כי היחס האסימפטוטי נשמר.
הסבירו מהי הבעיה הלוגית בשיטתה של פרופסור אילוביץ'.

ii. (6 נקודות) יש לקבוע ולהוכיח האם מתקיים

f (n) = Θ (g (n))

או

f (n) = ω (g (n))

או

f (n) = o (g (n))

.
שימו לב לא לכתוב "מתקיים יחס

o

", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר ב

★★★★★

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

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 2 T (\frac{2 n}{3}) + 5 n \cdot lo g^{3} (n) i f n = 1 i f n > 1

ב) (12 נקודות) הוכיחו או הפריכו כל אחת מהטענות הבאה:

i.

2^{n} = Θ (2^{2 + n})

ii.

2^{n} = Θ (2^{2 \cdot n})

הערה: ניתן להפריך יחס

f (n) = Θ (g (n))

ע"י הוכחה שמתקיים יחס

f (n) = ω (g (n))

, או יחס

f (n) = o (g (n))

.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר ב

★★★★★

נוסחת נסיגהמשפט האבסימון אסימפטוטיניתוח אלגוריתמיםהשוואת פונקציותאסימפטוטיקה

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 4 T (\frac{n}{4}) + n + \frac{1}{n} i f n = 1 i f n > 1

ב) (12 נקודות) להלן שתי פונקציות

f, g : N \to R^{+}

. יש לקבוע ולהוכיח האם מתקיים

f (n) = o (g (n))

או

f (n) = ω (g (n))

או

f (n) = Θ (g (n))

.
שימו לב לא לכתוב "מתקיים יחס o", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

f (n) = n^{10 l o g n}

g (n) = (lo g n)^{n}

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר ב

★★★★★

נוסחת נסיגהמשפט האבסימון אסימפטוטיניתוח אלגוריתמיםהשוואת פונקציותאסימפטוטיקה

א) (15 נק') הוכיחו או הפריכו את הטענה הבאה:
לכל

f, g

פונקציות מהטבעיים לטבעיים,
אם

f (n) = O (g (n))

אז

f (n) + g (n) = Θ (g (n))

.
יש להוכיח על פי ההגדרה או להפריך ע"י דוגמא נגדית.

ב) (10 נק') להלן שתי פונקציות

f, g : N \to R^{+}

. יש לקבוע ולהוכיח האם מתקיים

f (n) = o (g (n))

או

f (n) = ω (g (n))

או

f (n) = Θ (g (n))

.
שימו לב לא לכתוב "מתקיים יחס o", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

f (n) = i = 0 \sum n - 1 \frac{1}{n - i}

g (n) = lo g (n^{2})

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר א

★★★★★

סימון אסימפטוטיהשוואת פונקציותאסימפטוטיקהניתוח אלגוריתמים

א) (13 נקודות) תהיינה

f, g : N \to R^{+}

נגדיר יחס חדש

O_{l}

עבור סעיף זה בלבד:
נגדיר ש-

f (n) = O_{l} (g (n))

אם קיים

ε > 0

שעבורו

f (n) = O (g (n) lo g^{ε} (n))

.

הוכיחו או הפריכו:
אם

f (n) = O_{l} (g (n))

וגם

g (n) = O_{l} (h (n))

אז

f (n) = O_{l} (h (n))

.
יש להוכיח או להפריך על פי ההגדרה.

ב) (12 נקודות) להלן שתי פונקציות

f, g : N \to R^{+}

. יש לקבוע ולהוכיח האם מתקיים

f (n) = Θ (g (n))

או

f (n) = ω (g (n))

או

f (n) = o (g (n))

.

שימו לב לא לכתוב "מתקיים יחס

o

", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

f (n) = i = 1 \sum n \frac{2 i ^{2} + 1}{i}

g (n) = n^{2} lo g (n)

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר א

★★★★★

סימון אסימפטוטיהשוואת פונקציותאסימפטוטיקההוכחת נכונותניתוח אלגוריתמים

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

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