דף 1 מתוך 1

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

נשלח: 15:42 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.
בשאלה בתרגול לא נתנו לנו שום הנחה על אורך המחרוזות. אז למה באמת התעלמו מהמקרה הגרוע ביותר?
מתי מותר גם לנו לעשות את זה?

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

נשלח: 16:06 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. שאליה ניתן להתייחס כקבוע. ממה שזכור לי לא ייתכן ומילה תשנה את אורכה,לרוב זה קבוע. ייתכן ואני טועה.

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

נשלח: 16:14 17/07/2010
על ידי jenia
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 .