مرتبه ی زمانی الگوریتم زیر رو از روش جایگذاری بدست اورده جاهایی که دورش خط کشیدم رو متوجه نمی شم
همچینن اگر نخواهیم از روش جایگذاری حل کنیم چطوری می تونیم مرتبه زمانی اش را بدست اوریم از طریق قضیه اصلی هم که نمی شود.
پاسخ:
(۱۱ خرداد ۱۳۹۴ ۰۹:۲۸ ق.ظ)gunnersregister نوشته شده توسط: پاسخ:واقعا نوشتن راههایی که شما زحمت کشیدین خیلی زیاد و حواس جمع زیاد می خوان پس چطوری تو کتاب عددهای ۴ و ۲ (جمله های دوتا به اخر مانده و یکی به اخر مانده ) را در اورده است و در آخر هم چطوری نوشته ۲n-2 ؟؟؟؟؟
این سوالو نخواهیم از روش جایگذاری و سری هندسی حل کنیم راه دیگه هم داره ؟
حل با روش اصلی:
[tex]T(n)=T(\frac{n}{2}) n\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: ,\: \: \: \: \: a=1\: \: \: \: \: \: \: ,\: \: b=2\: \: \: \: \: \: \: \: \: \: ,\: \: \: \: \: \: \: \: \: c=1[/tex]
[tex]c>\log_b^a\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: ,\: \: \: \: \: \: \: \: 1>0[/tex]
پس خواهیم داشت:
[tex]T(n)=\theta(n)[/tex]
البته با حفظ این شرط که باید: [tex]f(n)=n\: \: [/tex]
[tex]a\cdot f(\frac{n}{b})<k\cdot f(n)\: \: \: \: \: \: \: \: \: \: ,\: \: \: \: \: \: \: k<1[/tex]
در اینجا داریم :
[tex]f(\frac{n}{2})<k\cdot f(n)\: \: \: \: \: \: \: \: \: \: ,\: \: \: \: f(n)=n\: ,\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \frac{n}{2}<k\cdot n\: \: ,\: \: \: k>\frac{1}{2}=0.5[/tex]
و این شرط برقراره پس حلموون از این روش مشکلی نداره.
قسمت اول سوالتون:
در واقع الگوی نوشتن من با متن کتاب شما یکیه چون :
[tex]your\: book\: :\: \: \: \: \: \: \: \: \: 1 2 4 \cdot\cdot\cdot \frac{n}{4} \frac{n}{2} n[/tex]
و حل من هم اینه:
[tex]My\: Solution\: :\: \: \: \: \: \: \: \: \: \: \: \: n \frac{n}{2} \frac{n}{4} \frac{n}{8} \cdot\cdot\cdot \frac{n}{\frac{n}{4}} \frac{n}{\frac{n}{2}} \frac{n}{n}=n \frac{n}{2} \frac{n}{4} \frac{n}{8} \cdot\cdot\cdot 4 2 1[/tex]
و هر دو تا حل تا به اینجا به یه عبارت یکسان میرسن.
قسمت اول سوالتون:
در واقع الگوی نوشتن من با متن کتاب شما یکیه چون :
[tex]your\: book\: :\: \: \: \: \: \: \: \: \: 1 2 4 \cdot\cdot\cdot \frac{n}{4} \frac{n}{2} n[/tex]
و حل من هم اینه:
[tex]My\: Solution\: :\: \: \: \: \: \: \: \: \: \: \: \: n \frac{n}{2} \frac{n}{4} \frac{n}{8} \cdot\cdot\cdot \frac{n}{\frac{n}{4}} \frac{n}{\frac{n}{2}} \frac{n}{n}=n \frac{n}{2} \frac{n}{4} \frac{n}{8} \cdot\cdot\cdot 4 2 1[/tex]
و هر دو تا حل تا به اینجا به یه عبارت یکسان میرسن.
[/quote]
نه نه من سوالم این نبود سوالم اینه که تو همین کتاب مدرسان چطوری بدون اینکه از روش سری هندسی بره ۲n-2 را در آخرین جمله بدست اورد ؟ یعنی با مثال ۲n-2 رو بدست اورد؟
نویسنده کتاب جمع دنباله اعداد حاصل از توانهای ۲ رو میدونسته و نخواسته با نوشتنش راه حلش رو طولانی کنه.
در پاسخ به سوالتون تو
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اوون قسمت از سوال رو که کامل ننوشتم اینجا مینویسم:
[tex]f(n)=\frac{n\cdot(n^{\log\: \frac{1}{2}}-1)}{-\frac{1}{2}} f(1)=\frac{n\cdot(n^{\log\: 1\: -\log\: 2}-1)}{-\frac{1}{2}} f(1)=\frac{n\cdot(n^{0-1}-1)}{-\frac{1}{2}} f(1)=\frac{n\cdot(n^{-1}-1)}{-\frac{1}{2}} f(1)[/tex]
[tex]=-2n(\frac{1}{n}-1) f(1)=-2 2n f(1)[/tex]