שלום לכולם,
הטפסים של מועד ב הוחזרו בדוקים למזכירות.
הציונים כנראה יהיו זמינים לכם בקרוב.
לציון המבחן הוספו 6 נקודות,
וכמו בדרך כלל, ציונים בין 55 ל-60 עוגלו ל-60.
הציון הסופי חושב כמו במועד א'.
שנה טובה,
יהב
Recent Forum Posts
הבנתי
תודה רבה!
חסם תחתון מדבר על לפחות.
כל התפצלות לוקחת לפחות זמן קבוע,
וכל האלגוריתם מיון דורש במקרה הגרוע שלו לפחות
n log n
זמן
אולי צריך יותר זמן בכל התפצלות, אבל אין לי אף דרך להוכיח את זה
הבנתי את החסם
m
אבל זה לא נכון להגיד שהמיון לוקח
nlogn
כי אנחנו לא יודעים מה אורך כל מילה חסר פה מידע
אתה אומר שאתם לא מצפים לזה ושאני יכול להניח שכל התפצלות לוקחת זמן קבוע?
וגם לא הבנתי את החסם
m
נגיד שכל המחרוזות זהות, ברור שאני צריך לעבור על כל האותיות, אבל למה זה מספיק?
איזה אלגוריתם פותר את המקרה הזה ב
m
?
הנקודה שחשוב להבין היא שעץ ההשוואות מתאר את ההתפצלויות שהאלגוריתם
יכול לבצע כתוצאה מהקלטים האפשריים בדרך לכל הפלטים האפשריים.
אנחנו לא יודעים כמה זמן מושקע בכל התפצלות, זה לא חייב להיות $\Omega(t)$ או כל זמן אחר,
לכן לשם החסם התחתון בשאלה זו אנחנו יכולים רק להניח עבודה קבועה בכל התפצלות.
הסדר הלא-לינארי של השיחה יצר קצת בלבול, לא עניתי לך לגבי חסם תחתון,
אלא למה זה לא נכון שדרוש זמן הריצה שציינת עבור הקלט המסויים.
החסם התחתון מורכב משני חלקים:
צריך לעבור על כל האותיות במקרה הגרוע (למשל שכל המחרוזות זהות),
ולכן נקבל $\Omega(m)$. בנוסף צריך למיין $n$ מחרוזות, לכן
יש $n!$ פלטים אפשריים. מכאן, עץ ההשואות של כל אלגוריתם הוא
בעומק $\Omega(n \log n)$, לא משנה מה אנחנו משווים.
סה"כ קיבלנו
$\Omega(m + n \log n)$.
אז לא הבנתי את הפתרון שלך…
איך אתה מגיע לחסם תחתון
nlogn?
הרי אתה לא יכול להשתמש במודל ההשוואות למילים כי אתה לא יכול להשוות בין מילים.
וגם החלק השני לא ברור
ברור שצריך לעבור על כל האותיות…
אני דיברתי על סעיף ג', כדוגמה נגדית לטענה שלך מ-17:24
תודה
על איזה סעיף אתה מדבר?
אני מדבר על סעיף ב
צריך להוכיח חסם תחתון למיון
n
מילים
באופן כללי
$O(f(n) + g(n))$
זה בדיוק אותו דבר כמו
$O(\max\{f(n),g(n)}\})$
עבור פונקציות שמתארות זמן ריצה (חיוביות, לא יורדות,…)
ההוכחה לפי ההגדרה -
כיוון אחד ברור כי הסכום גדול מהמקסימום,
בכיוון השני ניקח את $n_0$ הגדול מבין השניים, ונכפיל ב-2 את $c$ הגדול מבין השניים,
כאשר $c, n_0$ הם כמו בהגדרה.
עבור האלגוריתם הספציפי שמופיע בשאלה זהו זמן הריצה.
בקריאה הראשונה אנחנו מוצאים את האות הראשונה החציונית.
כל האותיות הראשונות, של כל המחרוזות, זהות לה,
ולכן תהיה קריאה רקורסיבית אחת, למיון כל המחרוזות לפי האות השניה.
הרקורסיה ממשיכה באופן דומה, עד שמגיעים לאות האחרונה.
מספר הקריאות הרקורסיביות הוא $O(t)$, זמן הריצה של כל קריאה הוא $O(n)$ וסה"כ קיבלנו:
$O(nt) = O(m)$
ועוד שאלה
כשמופיע בביטוי לסיבוכיות חיבור של שני איברים האם הכוונה לגדול מיביניהם
לדוג'
O(m+nlogn)=MAX(O(m)+O(nlogn))
לא הבנתי…
אתה יכול להסביר למה במקרה שכל המחרוזות שוות הזמן הוא
m
?
אני מדבר על מחרוזות שוות לא אותיות שוות
כלומר משהו בסגנון:
צמנ צמנ צמנ צמנ צמנ
כאשר t=3 n=5 m=15
אין קשר בין הדברים.
העובדה שבמקרה הגרוע תשווה שתי מחרוזות בזמן $O(t)$
לא אומרת שכל השוואה שתבצע תהיה בין שתי מחרוזות שלמות ותיקח את הזמן הזה
האלגוריתם משווה אות-אחר-אות וכך חוסך את ההשוואות המלאות,
כי אם האותיות שונות, לא צריך להמשיך ולהשוות את המחרוזות.
אני יודע שאני לא חייב להשוות את כל המילה אבל במקרה הגרוע אני כן אצטרך לעבור על כל המילה כלומר לעבור אות אות ולהשוות, וזה יקח
O(t)
לפי מודל ההשוואות אני אצטרך לבצע
nlogn
השוואות של מילים
ולכן סה"כ
t*n*logn=mlogn
אולי לא הבנתי את האלגוריתם ?
ועומק העץ הוא $\Omega(n \log n)$ כי יש $n!$ פלטים אפשריים.
אין שום דבר שמכריח אותך להשוות תמיד שתי מילים בזמן $\Omega(t)$ ולא להשוות אות-אות
תבחן את הדוגמה שלך, ותריץ עליה את האלגוריתם מסעיף ג', אם תעשה את זה תגלה שזה דווקא
המקרה הקל של האלגוריתם, האלגוריתם ירוץ בזמן $O(m)$ במקרה המסויים הזה שבו כל המחרוזות זהות.
אם הקלט יהיה רשימה של מילים זהות הסיבוכיות תיהיה
mlogn
לא?
