שאלה 6 סעיף ב

מנהל: TA_Isana

שלח תגובה
נועה
הודעות: 29
הצטרף: 00:26 25/10/2009

שאלה 6 סעיף ב

שליחה על ידי נועה » 21:19 14/06/2010

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

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: שאלה 6 סעיף ב

שליחה על ידי TA_Yakim » 08:45 15/06/2010

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

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה 6 סעיף ב

שליחה על ידי michal cohen » 22:47 15/06/2010

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

zvikadori
הודעות: 10
הצטרף: 23:45 19/10/2009

Re: שאלה 6 סעיף ב

שליחה על ידי zvikadori » 23:56 15/06/2010

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

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

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

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

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: שאלה 6 סעיף ב

שליחה על ידי TA_Yakim » 17:20 16/06/2010

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

zvikadori
הודעות: 10
הצטרף: 23:45 19/10/2009

Re: שאלה 6 סעיף ב

שליחה על ידי zvikadori » 19:52 16/06/2010

תודה רבה!!!

נועה
הודעות: 29
הצטרף: 00:26 25/10/2009

Re: שאלה 6 סעיף ב

שליחה על ידי נועה » 21:46 16/06/2010

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

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: שאלה 6 סעיף ב

שליחה על ידי TA_Yakim » 23:26 16/06/2010

נועה שלום

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

בהצלחה

שלח תגובה

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