سلام
لطفا یکی مرتبه زمانی تابع T(n) = 2T(n/2) + n/logn با روش تغییر متغیر توضیح بده.
ممنون
این سوال با درخت راحت تر حل میشه...اگه بخواهید من بروش درخت بهتون توضیح میدم
به روش تغییر متغیر :
n=2^k =>T(2^k)=2T(2^k-1)+2^k/k
hameye moadele ro taghsim bar 2^k mikonim badesh taghire nam midim.
s(k) =s(k-1)+1/k
ke inam rahat hal mishe.
Sent from my Nexus 7 using Tapatalk
به جایn, مقدار [tex]2^k[/tex] را قرار می دهیم
و معادله ی زیر به دست میاد
[tex]T(2^k)=2T(\frac{2^k}{2}) \frac{2^k}{\log 2^k}[/tex]
خب می دانیم که در تقسیم دو عدد توان دار با پایه های یکسان توان ها از هم کم می شوند
پس [tex]\frac{2^k}{2}=2^{k-1}[/tex]
از طرفی می دانیم که در لگاریتم توان به ضریب تبدیل می شود پس:
[tex]\log2^k=klog_22=k[/tex]
حالا می بیینم متغیر های T در وراقع توان ها هستند یعنی چیزی ه دارد در ورودی های T عوض می شوند توان است
پس به جای کار کردن با اعداد های توان دار با خود توان ها کار می کنیم
یه تابع جدید تعریف می کنیم که به جای وابسته بودن به یک عدد توان دار به خود توان وابسته باشد
مثلا:
[tex]T(2^k)=S(k)[/tex]
پس معادله ی بالا رو می شه به این صورت بازنویسی کرد:
[tex]S(k)=2S(k-1) \frac{2^k}{\k}[/tex]
اسم این معدله رو می ذاریم *
حالا باید زمان این معادله رو بدست بیاریم:
من از روش جایگذاری حل می کنم
s(k) به S(k-1) وابسته س خب مقدار S(k-1) چیست؟
اگه تو همون معادله * به جای K، عدد k-1 بذارم بدست میاد میشه :
[tex]S(k-1)=2S(k-2) \frac{2^{k-1}}{k-1}[/tex]
خب حالا این رو تو معادله قبلی جایگذاری می کنم میشه:
[tex]S(k)=2(2S(k-2) \frac{2^{k-1}}{k-1}) \frac{2^k}{k}[/tex]
[tex]S(k)=4S(k-2) \frac{2^k}{k-1} \frac{2^k}{k}[/tex]
خب حالا مقدار S(k-2) چیست؟
اگه تو همون معادله * به جای K، عدد k-2 بذارم بدست میاد میشه :
[tex]S(k-2)=2S(k-3) \frac{2^{k-2}}{k-2}[/tex]
که اگه تو معدله قبلی بذارم می شه:
[tex]S(k)=4\: (2S(k-3) \frac{2^{k-2}}{k-2}) \frac{2^k}{k-1} \frac{2^k}{k}[/tex]
[tex]S(k)=8S(k-3) \frac{2^k}{k-2} \frac{2^k}{k-1} \frac{2^k}{k}[/tex]
خب دیگه بقیه ش واضحه
واضحه که هر چی به عقب بریم صورت تغییری نمی کنه و فقط یه واحد از مخرج کم می شه
با خودمون می گیم این روند تا ککی ادامه داره؟
تا وقتی که مخرج به عدد ۱ برسه پس می توان معادله * را به این صورت باز کرد:
[tex]S(k)=\frac{2^k}{1} \frac{2^k}{2} ... \frac{2^k}{k-2} \frac{2^k}{k-1} \frac{2^k}{k}[/tex]
خب حالا از مقدار دو به توان k فاکتور می گیریم:
[tex]S(k)=2^k(\frac{1}{1} \frac{1}{2} ... \frac{1}{k-2} \frac{1}{k-1} \frac{1}{k})[/tex]
مقدار داخل پرانتز رومی دانیم برابر است با logk
پس:
[tex]S(k)=2^k\: \log k[/tex]
اما این پیچیدگی S(k) است نه T(n).
یادمونه که چجوری T(2^k) رو برابر S(k) قرار دادیم
و می دانیم وقتی n برابر است با دو به توان k
پس k برابر است با logn
[tex]T(n)=T(2^k)=S(k)=O(2^k\log k)=O(nloglogn)[/tex]
سلام خانم fatemeh69 از پاسخ جامع و کاملی که برای این سوال ارائه دادید ممنونم. فقط بنده یه مشکلی دارم و می خوام بدونم شما به هنگام تعیین مرتبه [tex]s(k)[/tex] حالت پایه [tex]s(0)=0[/tex] رو از کجا فهمیدید؟
(۲۱ مرداد ۱۳۹۳ ۱۰:۳۸ ب.ظ)bahman2000 نوشته شده توسط: سلام خانم fatemeh69 از پاسخ جامع و کاملی که برای این سوال ارائه دادید ممنونم. فقط بنده یه مشکلی دارم و می خوام بدونم شما به هنگام تعیین مرتبه [tex]s(k)[/tex] حالت پایه [tex]s(0)=0[/tex] رو از کجا فهمیدید؟می دونیم که S(0) بالاخره مساوی با یه عددی است (منظورم اینه که مساوی با یه تابع یا وابسته به متغیری نیست)
پس نهایتا s(0) مساوی هر عددی باشه بالاخره تو پیچیدگی تاثیری نداره چون [tex]2^k\log k[/tex] به علاوه یه عددی (که نمی دونیم چیه از مرتبه ی [tex]2^k\log k[/tex]است و مقدار اون عدد تو پیچیدگی تاثیری نداره
(۲۱ مرداد ۱۳۹۳ ۰۷:۵۷ ب.ظ)fatemeh69 نوشته شده توسط: سلام ممنون از توضیحات کاملتون
برای من یه سوال پیش اومد:
چرا وقتی این جایگزینی رو انجام دادین:
[tex]T(2^k)=S(k)[/tex]
[tex]S(k)=2S(k-1) \frac{2^k}{k}[/tex]
کسری که در آخر هست رو نغییر ندادید؟ مگرنه باید هرجایی که ۲ به توان k هست رو باید با k جایگزین کرد؟!
پس معادله ی بالا رو باید به این صورت بازنویسی کرد:
[tex]S(k)=2S(k-1) \frac{k}{logk}[/tex]
ممنون میشم اگه جواب بدید
(۲۲ مرداد ۱۳۹۳ ۰۹:۳۹ ق.ظ)reza777gh نوشته شده توسط: کسری که در آخر هست رو نغییر ندادید؟ مگرنه باید هرجایی که ۲ به توان k هست رو باید با k جایگزین کرد؟!
پس معادله ی بالا رو باید به این صورت بازنویسی کرد:
[tex]S(k)=2S(k-1) \frac{k}{logk}[/tex]
ممنون میشم اگه جواب بدید
خیر ما فقط نماد گذاری رو عوض کردیم
ما تصمیم کرفتیم از یه جایی به بعد به جای هر نماد [tex]T(2^k)[/tex] ای که دیدیم به جاش S(k) بذاریم
تابع [tex]T(2^k)[/tex] یه تابعی بوده بر حسب دو به توان K
یعنی دو به توان k رو می گرفته یه بلاهایی سرش در می آورده یه خروجی به ما می داده
حالا ما میگیم ما یه تابع نظیر داریم که همین کارهارو رو k انجام می ده یعنی این تابع ما به جای این که دو به توان k بگیره و یه خروجی بده عدد k رو می گیره و همون خروجی تابع T رو می ده.
و ما از این تساوی [tex]T(2^k)=S(k)[/tex] فقط برابر بودن این دو تابع به ازای مقادیر متناسب ورودی شونو می شناسیم و با دیدن ایk تساوی نمی تونیم بفهیمم که دو به توان k را باید با k جایگذاری کرد.
اگر بخواهیم بدانیم طبق این تساوی دو به توان k را باید با چه چیزی جایگذاری کرد از طرفین تساوی [tex]T(2^k)=S(k)[/tex] عملگر [tex]T^{-1}[/tex]می گیریم پس می شود:
[tex]2^k=T^{-1}(S(k))[/tex]
پس از تساوی فوق به این نتیجه می رسیم که باید به جای هر [tex]2^k[/tex] مقدار [tex]T^{-1}(S(k))[/tex] را قرار دهیم (نه مقدار k)
(۲۲ مرداد ۱۳۹۳ ۱۱:۰۲ ق.ظ)fatemeh69 نوشته شده توسط: خیر ما فقط نماد گذاری رو عوض کردیم
ما تصمیم کرفتیم از یه جایی به بعد به جای هر نماد [tex]T(2^k)[/tex] ای که دیدیم به جاش S(k) بذاریم
تابع [tex]T(2^k)[/tex] یه تابعی بوده بر حسب دو به توان K
یعنی دو به توان k رو می گرفته یه بلاهایی سرش در می آورده یه خروجی به ما می داده
حالا ما میگیم ما یه تابع نظیر داریم که همین کارهارو رو k انجام می ده یعنی این تابع ما به جای این که دو به توان k بگیره و یه خروجی بده عدد k رو می گیره و همون خروجی تابع T رو می ده.
و ما از این تساوی [tex]T(2^k)=S(k)[/tex] فقط برابر بودن این دو تابع به ازای مقادیر متناسب ورودی شونو می شناسیم و با دیدن ایk تساوی نمی تونیم بفهیمم که دو به توان k را باید با k جایگذاری کرد.
اگر بخواهیم بدانیم طبق این تساوی دو به توان k را باید با چه چیزی جایگذاری کرد از طرفین تساوی [tex]T(2^k)=S(k)[/tex] عملگر [tex]T^{-1}[/tex]می گیریم پس می شود:
[tex]2^k=T^{-1}(S(k))[/tex]
پس از تساوی فوق به این نتیجه می رسیم که باید به جای هر [tex]2^k[/tex] مقدار [tex]T^{-1}(S(k))[/tex] را قرار دهیم (نه مقدار k)
من خیلی وقته که دنبال فهمیدن این روش هستم و خیلی خوشحال شدم که دیدم به این خوبی توضیح دادی شما
فکر کنم با مبحث لاپلاس درس معادلات(که اون رو هم بلد نیستم
) قاطی کردم!واقعا ممنون!