שאלה לגבי שאלה 4 בתרגול 11

מנהל: TA_Isana

שאלה לגבי שאלה 4 בתרגול 11

הודעהעל ידי jenia » 14:42 17/07/2010

בשאלה אנחנו מתבקשים למיין n מחרוזות שאורכן לא קבוע ב- (O(n לפי סדר לקסיקוגרפי.
בקורמן מופיעה אותה שאלה (8.3 בעמ' 158, במהדורה השנייה למי שממש מתעקש לבדוק :P). בתשובה שלהם הם אומרים שהפתרון שניתן בתרגול אינו נכון בהכרח.
נכתב שם שהמקרה הגרוע ביותר הוא מחרוזת אחת באורך n/2 ושאר n/2 המחרוזות באורך 1. ואז רדיקס ירוץ ב- ( O(n/2(n/2+1)=O(n^2.
בשאלה בתרגול לא נתנו לנו שום הנחה על אורך המחרוזות. אז למה באמת התעלמו מהמקרה הגרוע ביותר?
מתי מותר גם לנו לעשות את זה?
jenia
 
הודעות: 4
הצטרף: 10:09 15/11/2009

Re: שאלה לגבי שאלה 4 בתרגול 11

הודעהעל ידי Brk » 15:06 17/07/2010

jenia כתב:בשאלה אנחנו מתבקשים למיין n מחרוזות שאורכן לא קבוע ב- (O(n לפי סדר לקסיקוגרפי.
בקורמן מופיעה אותה שאלה (8.3 בעמ' 158, במהדורה השנייה למי שממש מתעקש לבדוק :P). בתשובה שלהם הם אומרים שהפתרון שניתן בתרגול אינו נכון בהכרח.
נכתב שם שהמקרה הגרוע ביותר הוא מחרוזת אחת באורך n/2 ושאר n/2 המחרוזות באורך 1. ואז רדיקס ירוץ ב- ( O(n/2(n/2+1)=O(n^2.
בשאלה בתרגול לא נתנו לנו שום הנחה על אורך המחרוזות. אז למה באמת התעלמו מהמקרה הגרוע ביותר?
מתי מותר גם לנו לעשות את זה?

בתירגול קבעו שהאורך המקסימלי של מילה הוא m. כלומר נתון לך קבוצה של מילים,מספר סופי של מילים,באופן ברור מחדו"א יש לזה איבר מקסימום,עם אורך סופי של מילה m. שאליה ניתן להתייחס כקבוע. ממה שזכור לי לא ייתכן ומילה תשנה את אורכה,לרוב זה קבוע. ייתכן ואני טועה.
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: שאלה לגבי שאלה 4 בתרגול 11

הודעהעל ידי jenia » 15:14 17/07/2010

Brk כתב:
jenia כתב:בשאלה אנחנו מתבקשים למיין n מחרוזות שאורכן לא קבוע ב- (O(n לפי סדר לקסיקוגרפי.
בקורמן מופיעה אותה שאלה (8.3 בעמ' 158, במהדורה השנייה למי שממש מתעקש לבדוק :P). בתשובה שלהם הם אומרים שהפתרון שניתן בתרגול אינו נכון בהכרח.
נכתב שם שהמקרה הגרוע ביותר הוא מחרוזת אחת באורך n/2 ושאר n/2 המחרוזות באורך 1. ואז רדיקס ירוץ ב- ( O(n/2(n/2+1)=O(n^2.
בשאלה בתרגול לא נתנו לנו שום הנחה על אורך המחרוזות. אז למה באמת התעלמו מהמקרה הגרוע ביותר?
מתי מותר גם לנו לעשות את זה?

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


ממה שזכור לי מהמקצוע הזה, הכוונה בקבוע היא לא שאורך המילה לא משתנה (מן הסתם), אלא שבהנתן n מילים אורך המילה המקסימלית לא תלוי n. אבל ברור שבהנתן 8 מחרוזות יכולה להיות מילה באורך 4 = n/2=8/2.
ואגב, בשאלה עצמה לא היה נתון שהאורך הוא קבוע. ההתייחסות לאורך המילה כ-m קבוע הופיעה רק בפתרון.
וזה בדיוק מה שאני שואלת. מתי אני יכולה להתעלם מהתלות האפשרית ב- n .
jenia
 
הודעות: 4
הצטרף: 10:09 15/11/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים