בתרגיל בית 9 שאלה 4 סעיף ב
יש
N מילים
M אותיות במילה
א"ב לא חסום.
צריך חסם תחתון למיון.
בתשובות שלכם כתבתם שמודל ההשואות תורם אומגה nlogn
המסקנה לגבי מודל ההשואות הגיע ע"י מציאת חסם תחתון למספר ההשוואות המינימלי שצריך כדי להגיע לעלה בעץ ההחלטה.
במקרה שלנו השוואה עולה במקרה הרע אורך של מילה.
אז למה מודל ההשוואות לא תורם
mnlogn
כחסם תחתון?
ראיתי במבחן מ2010 (סמסטר א מועד ב שאלה 2 ) שאלה מאוד דומה שמבקשים למיין עמודות מטריצה, למיטב הבנתי השאלות האלה זהות.
האמנם?
אם לא אז מה התשובה שם?