מבחן 2008 מועד א

[lironsam]

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

2.א

ו2.ב- בגלל שK קבוע אז אפשר לעשות מיון הכנסה בO(n) ?

[ronenhe]

לגבי 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ג אני לא בטוח ולא רוצה להטעות...
המון בהצלחה במועד ב!