מבחן 2008 מועד א

מנהל: TA_Isana

מבחן 2008 מועד א

הודעהעל ידי lironsam » 11:28 15/07/2010

היי
אפשר בבקשה הסבר על תרגילים:
1.ג
לא הבנתי איך הם הגיעו לזה .... עשיתי לפי הנוסחה של הגובה קטן שווה לlog בבסיס 6 של (n+1)/2 אבל זה לא יצא לי אותו דבר החזקה יצאה לי רק על ה t
ויצא לי שהn בכלל גדול מהביטוי ולא קטן ממנו.....
אז כנראה שזו לא הדרך :)
אז איך הם הגיעו לתשובה?

2.א

ו2.ב- בגלל שK קבוע אז אפשר לעשות מיון הכנסה בO(n) ?
lironsam
 
הודעות: 25
הצטרף: 23:12 04/12/2009

Re: מבחן 2008 מועד א

הודעהעל ידי ronenhe » 12:07 15/07/2010

לגבי 2א:
דבר ראשון אפשר לעבוד בשיטת האלמינציה..
יש לך n^3 איברים אז לא יכול להיות שלא תעשה n^3 פעולות..
עכשיו הדילמה שלך היא לגבי 2 או 3
ברור למעשה שאין משמעות ללוג בריבוע כי יש לך אן בשלישית איברים אז לוג של אן בשלישית זה כמו לוג של אן
בתכלס התשובה הפשוטה ביותר אמורה להיות
xlogx
לא משנה מה יש לך וכמה במקרה שלך
x=n^3
ואז בדיוק לפי מה שאמרתי למעלה
לכן גם בלי להתעמק יותר מדי בשאלה (למרות שקראתי אותה פעמיים ההתלבטות היחידה יכולה להיות או 2 או 5.. וסביר להניח ש5 לא הנכונה אז 2)
בכל מקרה התשובה היא 2 משני הסיבות שרשמתי..

לגבי 2ב:
המספר שלך K קבוע עבור n>>k תקבל למעשה שיש לך מיון הכנה למערך בגודל 2k איברים (שזה גודל קבוע) ואז תרוץ אן פעמים על המערך (פעמיים) והנה קיבלת מיון ספירה קלאסי..
בכל מקרה זאת הדרך הקלאסית לפתור..
ועכשיו לשלילות:
4 לא יכול להיות כי הוא הרבה יותר גרוע ממיון ערימות רגיל
1 כנראה שגם לא נכון כי זה הפתרון הנאיבי
3 זה הפתרון הנאיבי הכי גרוע
עכשיו נשארה התלבטות בין 2 ל 5 :
K קבוע.. לוג של k גם יהיה קבוע
אבל יכול להיות לך k שהלוג שלו יהיה גדול מ2.. ואז זה יותר גרוע מהנאיבי..
כל הדרכים מובילות ל2..

אני בכוונה נותן לך 2 דרכים לפתור ככה שאם במבחן אתה נתקע תהיה לך אפשרות לדבג את עצמך ולראות אם אתה בכלל בכיוון..

לגבי 1ג אני לא בטוח ולא רוצה להטעות...
המון בהצלחה במועד ב!
ronenhe
 
הודעות: 182
הצטרף: 10:27 28/10/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים