איך אני ניגש לכזה תרגיל ?

איך פותרים את זה ??

א. נתון שזמן הריצה T(n) של אלגוריתם כלשהו מקיים: T(1) = q(1), T(n) = T(n/2) + W(n)

וכן T(n) = 2T(n/2) + O(n). טענה: T(n) = q(n) . (אפשר להיעזר בנוסחת האב).

נכון\לא נכון

נימוק:

אם הבנתי נכון את הסימונים שלך, הרי שאפשר לומר כך:

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. אז נראה לא נכון.

אוקיי

אבל מבחינה מתמטית אני ראיתי באיזשהו מקום אפשרות לפתיחה של עץ

ואפשר להגיע איתו להבנה שזה לא נכון

זה מה שאני רוצה ללמוד לעשות

כי באותה מידה זה יכלה להיות שאלה של נכון...והוכחה

- - - תגובה אוחדה: - - -

זו השאלה.

סליחה על ההעתקה היא הייתה גרועה

פתיחה של עץ זה בדיוק מה שעשיתי (רק שלא הראיתי את שלבי הביניים).

קח את התנאי הראשון:

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)

תודה רבה !!!

רק איך בידיוק נוסחת האב מתקשרת לי כאן ?

(אני פשוט רוצה לפשט לי את כל הסיפור הזה )

נוסחת האב / שיטת האב היא דרך לפתור באופן כללי נוסחאות נסיגה כמו אלה.

http://he.wikipedia.org/wiki/%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%90%D7%91

במקרים פשוטים אפשר להסתדר גם בלעדיה.