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

מנהל: TA_Isana

שלח תגובה
segev
הודעות: 50
הצטרף: 17:11 12/11/2009

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

שליחה על ידי segev » 15:02 23/06/2010

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

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

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

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

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

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

segev
הודעות: 50
הצטרף: 17:11 12/11/2009

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

שליחה על ידי segev » 17:53 23/06/2010

תודה רבה.

kes6
הודעות: 25
הצטרף: 12:14 22/09/2008

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

שליחה על ידי kes6 » 10:48 25/06/2010

רגע -

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

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

barzilai
הודעות: 5
הצטרף: 19:54 29/12/2009

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

שליחה על ידי barzilai » 10:57 25/06/2010

לפי חוקי לוגים, החזקה השלישית יוצאת החוצה לפני הלוג, ולכן יש כפל בקבוע (ב-3), ולכן אין משמעות לחזקה השלישית

talshum
הודעות: 25
הצטרף: 20:54 28/10/2009

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

שליחה על ידי talshum » 17:02 25/06/2010

נדב, (נראה לי שזה אתה, בריזלי)

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

kes6
הודעות: 25
הצטרף: 12:14 22/09/2008

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

שליחה על ידי kes6 » 17:42 25/06/2010

הטעות היתה אצלי, הביטוי שאני כתבתי לא היה נכון.

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

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

kes6
הודעות: 25
הצטרף: 12:14 22/09/2008

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

שליחה על ידי kes6 » 17:46 25/06/2010

O(n*log(n)) 1, כמובן.

שלח תגובה

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