תרגיל

השוואת קצבי גידול ביחס לאורך הקלט

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

מופעים קשורים בבחינות ובמטלות

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

q-1edfed327768נתונות שבע מחלקות סיבוכיות: P,quad EXP,quad DTime(2 n 6),quad c 1DTime(n 2 c),quad c 1DTime(c cn),quad c 1DTime(c n c),quad c 1DTime(n n c). סדרו אותן…0 בחינות · 1 מטלות · שיעורים 1, 2, 3, 10, 18 q-b944c700db52נתונות שבע מחלקות הסיבוכיות: P,quad EXP,quad DTime(2 n 6),quad c 1DTime(n 2 c),quad c 1DTime(c cn),quad c 1DTime(c n c),quad c 1DTime(n n c). סדרו את…0 בחינות · 1 מטלות · שיעורים 1, 2, 3, 10, 18

שאלה

בקלט נתון מספר חיובי $N$ בקידוד בינארי, ולכן אורך השדה הוא $n=\lceil\log_2(N+1)\rceil$ . דרגו את

(\log N)^4,\quad N^{1/3},\quad 2^{\sqrt{\log N}},\quad N\log N,\quad 2^N

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

דרישות קדם

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

רמז 1

תחילה דרגו כפונקציות של $N$ , ורק אחר כך הציבו $N=2^{\Theta(n)}$ .

רמז 2

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

רמז 3

כתבו $N^c=2^{c\log N}$ כדי להשוות לחזקות של $N$ .

פתרון מלא

נסמן $L=\log_2N$ . לאחר לקיחת לוגריתמים מתקבלים סולמות המעריכים $4\log L,\sqrt L,L/3,L+\log L,N$ . מאחר ש- $\log L=o(\sqrt L)$ ו- $\sqrt L=o(L)$ ,

(\log N)^4\ll2^{\sqrt{\log N}}\ll N^{1/3}\ll N\log N\ll2^N.

בפרט, לכל $\varepsilon>0$ ,

\frac{2^{\sqrt L}}{L^4}=2^{\sqrt L-4\log L}\to\infty,\qquad \frac{2^{\sqrt L}}{N^\varepsilon}=2^{\sqrt L-\varepsilon L}\to0.

לכן הביטוי השני גדול מכל פולילוגריתם קבוע אך קטן מכל חזקה חיובית של $N$ .

כעת מודדים לפי אורך הקידוד. מן האי־שוויון $2^{n-1}\le N<2^n$ נקבל

(\log N)^4=\Theta(n^4),\quad 2^{\sqrt{\log N}}=2^{\Theta(\sqrt n)},\quad N^{1/3}=2^{\Theta(n)},\quad N\log N=2^{\Theta(n)},\quad 2^N=2^{2^{\Theta(n)}}.

הראשון פולינומי. השני על־פולינומי, כי לכל קבוע $k$ מתקיים $\sqrt n-k\log n\to\infty$ , אך הוא תת־אקספוננציאלי כי $\sqrt n=o(n)$ . הביטויים השלישי והרביעי אקספוננציאליים יחידים, והאחרון דו־אקספוננציאלי.

המסקנה החשובה היא שהכינוי ״פולינומי״ תמיד מתייחס לאורך המחרוזת המקודדת. זמן $O(N)$ הוא פולינומי כאשר $N$ פריטים מופיעים במפורש, אך עלול להיות אקספוננציאלי כאשר $N$ הוא ערך של שדה בינארי. עיגול בתקרת הלוגריתם ושינוי בסיס הלוגריתם מוסיפים רק קבועים ולכן אינם משנים את הדירוג.

נקודות בדיקה

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

טעויות נפוצות

דירוג בלי לקבוע מדד גודל.
כינוי $2^{\sqrt n}$ פולינומי.
התייחסות ל- $2^N$ כאקספוננציאלי יחיד ב- $\log N$ .

מקורות ואימות

Merged summary, pp. 8-13
2026 transcript 1
Sipser 3e, sec. 7.1
מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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