۰
subtitle
ارسال: #۱
  
روش جایگذاری ۳
مرتبه ی زمانی الگوریتم زیر رو از روش جایگذاری بدست اورده جاهایی که دورش خط کشیدم رو متوجه نمی شم
همچینن اگر نخواهیم از روش جایگذاری حل کنیم چطوری می تونیم مرتبه زمانی اش را بدست اوریم از طریق قضیه اصلی هم که نمی شود.
همچینن اگر نخواهیم از روش جایگذاری حل کنیم چطوری می تونیم مرتبه زمانی اش را بدست اوریم از طریق قضیه اصلی هم که نمی شود.
۰
ارسال: #۳
  
RE: روش جایگذاری ۳
۰
ارسال: #۴
  
RE: روش جایگذاری ۳
با استفاده از [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]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]
مطمئن باشید اوون قسمت از جواب کتاب اشتباهه.(کدوم کتابه؟؟؟)
ولی روشهای حل متعددی برای اینگونه از سوالات است: روش اصلی، روش درختی و روش جایگزینی
ارسال: #۵
  
RE: روش جایگذاری ۳
(۱۱ خرداد ۱۳۹۴ ۰۱:۱۵ ب.ظ)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]
مطمئن باشید اوون قسمت از جواب کتاب اشتباهه.(کدوم کتابه؟؟؟)
ولی روشهای حل متعددی برای اینگونه از سوالات است: روش اصلی، روش درختی و روش جایگزینی
۰
ارسال: #۶
  
RE: روش جایگذاری ۳
بله. باز هم میشه استفاده کرد فقط باید شرایط اوون قضیه رو رعایت کنیم. مثلا اگه در صورت مسئله داشته باشیم:
[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]
[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]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close