שאלה 6 סעיף ב

[נועה]

שלום,
בשאלה זו ניתן לחלק את היחסים בין m,n,k להמון אפשרויות כך שעבור על אחת ננהג באופן שונה. עד לאיזו רמה לרדת בחלוקה למקרים?
לדוגמא אפשר להתייחס ל(m = O(logn או m=O(n) או m=O(n^2) וכו ולקבל תשובות שונות

[TA_Yakim]

התשובה צריכה להיות כוללנית
כלומר עד כך וכך עשה... בין כך לכך עשה... מעל כך וכך עשה...
מקווה שזה עוזר

[michal cohen]

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

[zvikadori]

מצטרף למיכל ולנועה...
יש כ"כ הרבה דרכים להשוות סדרי גודל(אולי בכלל אתם מתכוונים להשוואה יבשה k<n<m לדוג', לכן יש 6 אופציות כאלה).

כיצד באמת נראית ההשוואה הזאת(אם אפשר לתת דוג' אחת)... רק כדי להבין כיצד מתבצעת ההשוואה בין סדרי הגודל.

*אציין שמשיחה שלי עם מספר סטודנטים, אף אחד לא הצליח לתת תשובה חד משמעית רצינית בנושא.

בתודה מראש,
צביקה

[TA_Yakim]

למשל: אם n =< log(m) and k =< m אז:

[zvikadori]

תודה רבה!!!

[נועה]

אני לא עדיין לא הבנתי, אם אני יורדת לרמה של log וכו' אני יכולה למצוא עשרות מקרים לבדיקה!!!

[TA_Yakim]

נועה שלום

אני לא יכול לעזור יותר מזה
לא צריך להפריד לכל המקרים האפשריים, צריך רק להפריד למקרים שרלוונטיים לבחירת איזה אלגוריתם להריץ. לדוגמא בסעיף א אם k<m או k<logm או k<root of m אין להפרדות אלה כל משמעות כי בכל המקרים האלה צריך להריץ את אותו האלגוריתם
בודאי שאין עניין בחלוקה לעשרות מקרים כי אנחנו מכירים רק כעשר אלגוריתמים אפשריים
בפתרון לא צריך להשתמש ביותר מ 3 אלגוריתמי מיון שונים שאנו מכירים (ועוד וריאציה נוספת של אחד מהם למי שיענה על השאלה אפילו יותרטוב ממה שנדרש או מצופה מכם)

בהצלחה