דף 1 מתוך 1

מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 15:02 23/06/2010
על ידי segev
מדוע זה יוצא חסם תחתון? יש באמת חשיבות לכך שאומרים לנו שכל איבר מופיע בדיוק פעמיים?
(הסעיף עם האן בשלישית איברים)
בתודה מראש,

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 16:23 23/06/2010
על ידי TA_Ariel
אין חשיבות לעובדה שכל איבר מופיע פעמיים(בשביל מיון...).
אין לך שום הנחות על המערך חוץ מזה לכן, כמו שנלמד בכיתה, nlogn הוא חסם תחתון על מיון במודל השוואות, כשn הוא מספר האיברים,
כאן מספר האיברים הוא n^3.

בגלל שאין שום שימוש אחר בn הזה, האמת היא שדי טיפשי לכנותו n^3. אפשר היה לקרוא לו n.
לסיכום, לא מהיכל התהילה של שאלות מבנה נתונים.

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 17:53 23/06/2010
על ידי segev
תודה רבה.

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 10:48 25/06/2010
על ידי kes6
רגע -

ההסבר אכן ברור, אבל מדוע אם כך התשובה היא (n^3*log(n , ולא n^3*(logn)^3, כלומר תשובה ג'?

תודה ושבת שלום

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 10:57 25/06/2010
על ידי barzilai
לפי חוקי לוגים, החזקה השלישית יוצאת החוצה לפני הלוג, ולכן יש כפל בקבוע (ב-3), ולכן אין משמעות לחזקה השלישית

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 17:02 25/06/2010
על ידי talshum
נדב, (נראה לי שזה אתה, בריזלי)

אני לא בטוח שה-3 יוצא לפני ה-N לפי חוקי חזקות זה קורה שהאיבר בתוך הלוג הוא בחזקת 3 ופה כל הלוג ככה...

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 17:42 25/06/2010
על ידי kes6
הטעות היתה אצלי, הביטוי שאני כתבתי לא היה נכון.

הפתרון הוא אכן -

n*log(n^3)=O(n) 1

Re: מבחן 2008 מועד א שאלה 2 סעיף א

נשלח: 17:46 25/06/2010
על ידי kes6
O(n*log(n)) 1, כמובן.