15-05-2015, 22:45
|
|
|
|
חבר מתאריך: 30.08.09
הודעות: 2,880
|
|
לצורך הנוחות תניח ש-n הוא חזקה של 2, נוסחת הנסיגה תהיה [tex]T(n)=T(n/2)+\theta(1)[/tex].
שזה כמובן [tex]\theta(logn)[/tex].
תחשוב שאתה כל פעם חוצה את n, עד שאתה מקבל קבוע כלשהו - למשל 2.
זה שקול לכמות הפעמים שצריך להכפיל את 2 בעצמו כדי לקבל את n, כלומר פתרון המשוואה [tex]2^x=n[/tex] שהוא במקרה גם [tex]x=log_2{n}[/tex].
_____________________________________
ציטוט:
במקור נכתב על ידי Michael Shermer
Smart people are very good at rationalizing things they came to believe for non-smart reasons.
|
|