مرتبه ی زمانی الگوریتم زیر رو از روش جایگذاری بدست اورده جاهایی که دورش خط کشیدم رو متوجه نمی شم
همچینن اگر نخواهیم از روش جایگذاری حل کنیم چطوری می تونیم مرتبه زمانی اش را بدست اوریم از طریق قضیه اصلی هم که نمی شود.
پاسخ:
(۱۱ خرداد ۱۳۹۴ ۰۹:۲۷ ق.ظ)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]
مطمئن باشید اوون قسمت از جواب کتاب اشتباهه.(کدوم کتابه؟؟؟)
ولی روشهای حل متعددی برای اینگونه از سوالات است: روش اصلی، روش درختی و روش جایگزینی
(۱۱ خرداد ۱۳۹۴ ۰۱:۱۵ ب.ظ)gunnersregister نوشته شده توسط: با استفاده از [tex]Master\: theorem[/tex] هم میشه به جواب رسید:آهان متوجه شدم فقط یه سوال دیگه اگه در قضیه اصلی [tex]F(n)[/tex] پارامتری از n نداشته باشه مثلا فقط یه عدد باشه باز هم می شه از قضیه اصلی استفاده کرد؟
[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]T(n)=9\cdot T(\frac{n}{3}) 7[/tex]
اوون وقت خواهیم داشت: [tex]f(n)=7\: \: \: \: \: \: \: \: \: f(n)=\theta(1)=\theta(n^0)\: \: \: \: \: c=0[/tex]