פורסם 2014 בפברואר 1711 שנים איך אני ניגש לכזה תרגיל ?איך פותרים את זה ??א. נתון שזמן הריצה T(n) של אלגוריתם כלשהו מקיים: T(1) = q(1), T(n) = T(n/2) + W(n) וכן T(n) = 2T(n/2) + O(n). טענה: T(n) = q(n) . (אפשר להיעזר בנוסחת האב).נכון\לא נכוןנימוק:
פורסם 2014 בפברואר 1711 שנים אם הבנתי נכון את הסימונים שלך, הרי שאפשר לומר כך:T(n) = T(n/2) + W(n) ==> T(n) = W(n)T(n) = 2T(n/2) + O(n) ==> T(n) = O(nlogn)יש דברים שהם ממש בין n לnlogn ואינם theta(n). למשל nloglogn. אז נראה לא נכון.
פורסם 2014 בפברואר 1711 שנים מחבר אוקייאבל מבחינה מתמטית אני ראיתי באיזשהו מקום אפשרות לפתיחה של עץואפשר להגיע איתו להבנה שזה לא נכוןזה מה שאני רוצה ללמוד לעשותכי באותה מידה זה יכלה להיות שאלה של נכון...והוכחה- - - תגובה אוחדה: - - -זו השאלה.סליחה על ההעתקה היא הייתה גרועה
פורסם 2014 בפברואר 1711 שנים פתיחה של עץ זה בדיוק מה שעשיתי (רק שלא הראיתי את שלבי הביניים).קח את התנאי הראשון:T(n) = T(n/2) + W(n) = W(n) +W(n/2) + W(n/4) + W(n/8) + ... = W(2n) = W(n)התנאי השני:T(n) = 2T(n/2) + O(n) = O(n) + 2O(n/2) + 4O(n/4) + ... = logn * O(n) = O(nlogn)
פורסם 2014 בפברואר 1711 שנים מחבר תודה רבה !!!רק איך בידיוק נוסחת האב מתקשרת לי כאן ?(אני פשוט רוצה לפשט לי את כל הסיפור הזה )
פורסם 2014 בפברואר 1711 שנים נוסחת האב / שיטת האב היא דרך לפתור באופן כללי נוסחאות נסיגה כמו אלה.http://he.wikipedia.org/wiki/%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%90%D7%91במקרים פשוטים אפשר להסתדר גם בלעדיה.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.