مرتبه ی زمانی الگوریتم زیر رو از روش جایگذاری بدست اورده جاهایی که دورش خط کشیدم رو متوجه نمی شم
همچینن اگر نخواهیم از روش جایگذاری حل کنیم چطوری می تونیم مرتبه زمانی اش را بدست اوریم از طریق قضیه اصلی هم که نمی شود.
(11 خرداد 1394 09:27 ق.ظ)gunnersregister نوشته شده توسط: [ -> ]پاسخ:
حالا اگه از سری هندسی نریم می شه بگید طبق جواب خود کتاب چرا شد n-1 اوجایی که دورش رو خط کشیدم
اگر همچین سوالی اومد و نخواهیم از روش جایگذاری یا سری هندسی بریم راه دیگه ای وجود داره چون از قضیه اصلی هم نمیشه حل کرد
با استفاده از [tex]Master\: theorem[/tex] هم میشه به جواب رسید:
[tex]T(n)=aT(\frac{n}{b}) f(n)[/tex]
[tex]a\ge1\: \: \: ,\: \: \: \: b>1[/tex]
و چون [tex]f(n)=O(n^c)[/tex] که [tex]c<\log^a_b[/tex] یعنی [tex]0<\log^2_2=1[/tex]
پس
[tex]T(n)=\theta(n^{\log_b^a})=\theta(n)[/tex]
و اما قسمت اول سوالتوون درباره [tex]n-1[/tex]
ما قراره حاصل جمع زیر رو پیدا کنیم:
[tex]1 2 4 8 \cdot\cdot\cdot \frac{n}{2} nf(\frac{n}{n})=1 2 4 8 \cdot\cdot\cdot \frac{n}{2} n[/tex]
واضحه که جمع این اعداد هیچ وقت [tex]n-1[/tex] نمیشه چون ما خودمون [tex]n[/tex] رو داریم و باید حاصل این جمع بزرگتر از اوون دربیاد.
با یه مثال حاصل جمع رو پیش بینی کنیم:
[tex]1 2 \frac{8}{2} 8=15=2\ast(8)-1[/tex]
[tex]1 2 4 \frac{16}{2} 16=31=2\ast(16)-1[/tex]
و در آخر :
[tex]1 2 4 \cdot\cdot\cdot \frac{n}{2} n=2\ast(n)-1[/tex]
مطمئن باشید اوون قسمت از جواب کتاب اشتباهه.(کدوم کتابه؟؟؟)
ولی روشهای حل متعددی برای اینگونه از سوالات است: روش اصلی، روش درختی و روش جایگزینی
(11 خرداد 1394 01:15 ب.ظ)gunnersregister نوشته شده توسط: [ -> ]با استفاده از [tex]Master\: theorem[/tex] هم میشه به جواب رسید:
[tex]T(n)=aT(\frac{n}{b}) f(n)[/tex]
[tex]a\ge1\: \: \: ,\: \: \: \: b>1[/tex]
و چون [tex]f(n)=O(n^c)[/tex] که [tex]c<\log^a_b[/tex] یعنی [tex]0<\log^2_2=1[/tex]
پس
[tex]T(n)=\theta(n^{\log_b^a})=\theta(n)[/tex]
و اما قسمت اول سوالتوون درباره [tex]n-1[/tex]
ما قراره حاصل جمع زیر رو پیدا کنیم:
[tex]1 2 4 8 \cdot\cdot\cdot \frac{n}{2} nf(\frac{n}{n})=1 2 4 8 \cdot\cdot\cdot \frac{n}{2} n[/tex]
واضحه که جمع این اعداد هیچ وقت [tex]n-1[/tex] نمیشه چون ما خودمون [tex]n[/tex] رو داریم و باید حاصل این جمع بزرگتر از اوون دربیاد.
با یه مثال حاصل جمع رو پیش بینی کنیم:
[tex]1 2 \frac{8}{2} 8=15=2\ast(8)-1[/tex]
[tex]1 2 4 \frac{16}{2} 16=31=2\ast(16)-1[/tex]
و در آخر :
[tex]1 2 4 \cdot\cdot\cdot \frac{n}{2} n=2\ast(n)-1[/tex]
مطمئن باشید اوون قسمت از جواب کتاب اشتباهه.(کدوم کتابه؟؟؟)
ولی روشهای حل متعددی برای اینگونه از سوالات است: روش اصلی، روش درختی و روش جایگزینی
آهان متوجه شدم فقط یه سوال دیگه اگه در قضیه اصلی [tex]F(n)[/tex] پارامتری از n نداشته باشه مثلا فقط یه عدد باشه باز هم می شه از قضیه اصلی استفاده کرد؟
بله. باز هم میشه استفاده کرد فقط باید شرایط اوون قضیه رو رعایت کنیم. مثلا اگه در صورت مسئله داشته باشیم:
[tex]T(n)=9\cdot T(\frac{n}{3}) 7[/tex]
اوون وقت خواهیم داشت: [tex]f(n)=7\: \: \: \: \: \: \: \: \: f(n)=\theta(1)=\theta(n^0)\: \: \: \: \: c=0[/tex]