(۲۷ شهریور ۱۳۸۹ ۰۱:۰۷ ق.ظ)yasemi نوشته شده توسط:  من نمی دونم این جواب رو چطور بدست آورد اونجای رو که با قرمز مشخص کردم رو اگه کسی بلده لطفا با توضیح کامل بگه که هم من متوجه بشم و هم اگه کسی دیگه هم بلد نبود متوجه بشه

ممنون

می تونی از کتاب clrs هم کمک بگیری. خیلی خوب گفته.

کسی هست کمکی به من کنه؟
الگوریتم kmp که تابع شکست رو

F(j)= largest k < such that p0 p1 p2 …..p k = p j-k pj-k+1 …. P j
اینجوری تعریف کرده مفهومش چیه؟

(۲۷ شهریور ۱۳۸۹ ۰۱:۰۷ ق.ظ)yasemi نوشته شده توسط:  من نمی دونم این جواب رو چطور بدست آورد اونجای رو که با قرمز مشخص کردم رو اگه کسی بلده لطفا با توضیح کامل بگه که هم من متوجه بشم و هم اگه کسی دیگه هم بلد نبود متوجه بشه

ممنون

همونطور که تو شکلی که خودتون قرار دادید درخت رسم میشه، در هر سطح درخت اعداد به دست اومده جمع میشن(که این جمع برابر(۹/۱۰)به توان i هستش)، حالا اگه ارتفاع درختو بدست بیارید و در کرانهای سیگما قرار بدید جواب بدست میاد

ارتفاع درخت برابر logn (بر مبنای ۲) خواهد بود چراکه در هر مرحله هر گره دو فرزند تولید میکنه (تا الان گزینه‌ها‌ی ۱ و ۲ خذف شدن)

با این حساب جواب میشه سیگمای ۹/۱۰ به توان i، i از صفر تا logn ولی چون کرانی که تو گزینه سه اومده از logn بزرگتره گزینه سه انتخاب میشه (به logn بر مبنای ۱۰/۷ عدد بدبد از logn بر مبنای دو سریعتر رشد می کنه پس سیکمای مربوط بهش بزرگتره)