בוחן 2002

מנהלים: TA_Isana, TA_Isana

ilyal
הודעות: 63
הצטרף: 10:27 30/03/2009

Re: בוחן 2002

שליחה על ידי ilyal » 23:50 21/04/2010

אין פה מה להציב ולהסתבך זה בסה"כ: T(n) = T(n/2) + n
ואת זה פותרים בשיטת האב (מקרה 3).

Raz.A
הודעות: 64
הצטרף: 22:00 26/10/2009

Re: בוחן 2002

שליחה על ידי Raz.A » 08:52 22/04/2010

abp כתב:אני חושבת שה2 הזה לא קשור לזמן ריצה.. פשוט התוצאה שהרקורסיה תתן תהיה כפול 2.. היה יכול להיות רשום שם גם 100..
ועם זה באמת 2T(n/2) זה אומר שיש שתי קריאות רקורסיביות כל פעם.. וזה לא קורה פה.
מקווה שזה באמת נכון :)
אתה צודק, זאת טעות לעשות מה שעשינו - יצירת נוסחאת נסיגה ולהכפיל ב2 כי זה היה נכון רק אם הוא היה מכפיל את ההדפסות ב-2 או משהו כזה
אבל זה בעצם LOG N הכפלות של 2 בעצמו + 2n הדפסות בסה"כ.. אחרי התיקון יצא O(n) באמת.

תודה,

ronenhe
הודעות: 182
הצטרף: 10:27 28/10/2009

Re: בוחן 2002

שליחה על ידי ronenhe » 11:36 22/04/2010

lironsam כתב:יש מצב שאתה מעלה בבקשה את הפתרון בדרך של ההחלפה?
לא הגעתי לאותה נוסחה כמו שלך ... :\
אני מאמין שאתה מדבר על 2 ב
תעשה איטרציות
זה די זהה לשאלה 4C בשיעורי בית
תגיע שמספר הריצות שלך זה
i=log(log(n))
קצת משחקים וזהו.
בהצלחה

House
הודעות: 3
הצטרף: 09:12 10/11/2009

Re: בוחן 2002

שליחה על ידי House » 11:39 22/04/2010

lironsam כתב:התשובה ב2ב יצאה לי 1

אני מצרפת סריקה...( יצא קצת מבולגן..)
התשובה יצאה לך בסדר גמור, גם לי יצא ככה. אבל זה 2- ב' כי זמן הריצה שמצאנו הוא 2 בחזקת, וזמני הריצה שנתונים הם בlogים. והתוצאה שיצאה שקולה לתוצאה של 2-ב' (תשובה 2 - log(n)).

eliranyo
הודעות: 25
הצטרף: 17:24 02/12/2009

Re: בוחן 2002

שליחה על ידי eliranyo » 12:55 22/04/2010

לזאתי עם הסריקה 2 בחזקת לוג לוג N זה LOGN

nitzanma
הודעות: 9
הצטרף: 17:06 16/12/2009

Re: בוחן 2002

שליחה על ידי nitzanma » 15:09 22/04/2010

לירון, תסתכלי בהרצאה של אירינה מתאריך 14 במרץ, היא נתנה שם את הדוגמא הזו

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

Re: בוחן 2002

שליחה על ידי michal cohen » 22:55 22/04/2010

למה בשאלה 4 א זה או של N בריבוע ולא או של N?
כי תכלם אפשר לייצב את זה כסיגמא של k מ-1 עד n של: n-2k
שזה מתפצל לשתי סיגמות -סיגמא של n מינוס סיגמא של 2k
שזה n^2-n^2+n שזה או של אן... לא?

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: בוחן 2002

שליחה על ידי בר כהן » 00:11 23/04/2010

אם תפתחי את הסיגמות עד הסוף יוצא לך
xxx (n^2)/2 -(n^2)/4 -n/2
שמזה נשאר לך 4 / (n^2-2n)

שלח תגובה

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