(۱۱ خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)IranianWizard نوشته شده توسط:  سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:

$T(n)\: =\: 2T(\sqrt{n})\: + Log\: n$

$n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)$

$\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)$

$\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)$

حال رابطه ی $F(m)\: =\: 2F(\frac{m}{2})\: +\: m$ رو حل می کنیم.

$F(m)=\theta(m\: log \: m)$

$T(n)=\theta\: (\log\: n\: .\: \log\log n\: )$

(۱۱ خرداد ۱۳۹۵ ۰۲:۳۲ ق.ظ)kamal3401 نوشته شده توسط:  

(11 خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)IranianWizard نوشته شده توسط:  سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:

$T(n)\: =\: 2T(\sqrt{n})\: + Log\: n$

$n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)$

$\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)$

$\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)$

حال رابطه ی $F(m)\: =\: 2F(\frac{m}{2})\: +\: m$ رو حل می کنیم.

$F(m)=\theta(m\: log \: m)$

$T(n)=\theta\: (\log\: n\: .\: \log\log n\: )$

چرا ما تو تغییر متغیر از ۲ به توان m استفاده کردیم؟

(۱۱ خرداد ۱۳۹۵ ۰۲:۴۱ ق.ظ)IranianWizard نوشته شده توسط:  

(11 خرداد ۱۳۹۵ ۰۲:۳۲ ق.ظ)kamal3401 نوشته شده توسط:  

(11 خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)IranianWizard نوشته شده توسط:  سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:

$T(n)\: =\: 2T(\sqrt{n})\: + Log\: n$

$n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)$

$\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)$

$\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)$

حال رابطه ی $F(m)\: =\: 2F(\frac{m}{2})\: +\: m$ رو حل می کنیم.

$F(m)=\theta(m\: log \: m)$

$T(n)=\theta\: (\log\: n\: .\: \log\log n\: )$

چرا ما تو تغییر متغیر از ۲ به توان m استفاده کردیم؟

خب پس از چی استفاده کنیم؟
باید یطوری رابطه رو ساده کنیم خب.
شما از ۳ به توان m استفاده کن.باز فرقی نداره.فقط باید این رادیکال رو برداریم