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