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