در ارسال ۴ من S را بعنوان رابطه ای فرضی که از T کوچکتره در نظر گرفتم.
بعد به روش خاصی که اونجا نوشته‌ام حد بالای S رو بدست آوردم.
و چون T>S هستش پس حد بالای S می شه حد پایین برای T .
در نتیجه در اون ارسال حد پایین برای T بدست آمد.
و با اون ۲ی توی مخرج هم اومدم حد بالای T رو یافتم.
و هر دو هم یکی شد.
نظرت چیه؟ساندویچش کنیم؟
(۲۲ بهمن ۱۳۹۰ ۱۲:۱۶ ق.ظ)sasanlive نوشته شده توسط:من ارتفاع درخت را باید ام بر روی ۲ به توان ای میگرفتم. که اشتباه یود. اما این کران بالا شما تعریف دقیق تری است(21 بهمن ۱۳۹۰ ۱۰:۰۹ ب.ظ)atharrashno نوشته شده توسط: حال اگر از قوانین لگاریتم استفاده کنیم خواهیم داشت:
[tex]O(N*N)[/tex]
[tex]T(n)=2T( rac{n}{logn}) 3n< T(n)=2T( rac{n}{2}) 3n=O(nlogn)[/tex]
پس مقدار مجانبیش حتما از nlogn کمتره.
باید یه کران پایینم براش پیدا کرد تا بشه ساندویچش کرد خورد.
[tex]\sqrt{n}[/tex]
(۲۲ بهمن ۱۳۹۰ ۱۰:۳۸ ب.ظ)yaali نوشته شده توسط: در ارسال ۴ من S را بعنوان رابطه ای فرضی که از T کوچکتره در نظر گرفتم.
بعد به روش خاصی که اونجا نوشته‌ام حد بالای S رو بدست آوردم.
و چون T>S هستش پس حد بالای S می شه حد پایین برای T .
در نتیجه در اون ارسال حد پایین برای T بدست آمد.
و با اون ۲ی توی مخرج هم اومدم حد بالای T رو یافتم.
و هر دو هم یکی شد.
نظرت چیه؟ساندویچش کنیم؟
الان به نظر شما با عوض کردن T به S رابطه تغییری میکنه:
[tex]T(n)=2T(\frac{n}{2}) T(\frac{n}{\sqrt{n}}) n= S(n)=2S(\frac{n}{2}) S(\frac{n}{\sqrt{n}}) n< T(n)=2T(\frac{n}{2}) T(\frac{n}{logn}}) n< T(n)=2T(\frac{n}{2}) T(\frac{n}{2}) n=S(n)=2S(\frac{n}{2}) S(\frac{n}{2}) n[/tex]
مسلما نه.
این همون حده بالایی که شما برای کران پایین پیدا کردین:[tex]S(n)=2S(\frac{n}{2}) S(\frac{n}{2}) n[/tex]
شما اومدین یکبار در مخرج بجای [tex]\sqrt{n}[/tex] مقدار ۲ قرار دادین که درسته از رابطه ای که در مخرجش [tex]\sqrt{n}[/tex] هست رابطه بزرگتره ولی از رابطه اصلیمونم بزرگتره و بجای حده پایین رفتین به حده بالاش و اینکار برای محاسبه حده پایین اشتباهه.
من کلا با ساندویچ کردن مشکلی ندارم هواپیما رو هم ساندویچ میکنم میخورم
.اما شما ۲ تا نونو گذاشتین یه ور دسته آدم سسی میشه
.
یکبار جواب رو کامل می گذارم. ببینید کجاش ایراد داره
این T هستش که رابطه اصلی ماست:
[tex]T(n)=2T(\frac{n}{2}) T(\frac{n}{logn}) n[/tex]
یافتن حد پایین T:
من S را بعنوان رابطه ای فرضی که از T کوچکتره در نظر گرفتم. یعنی شبیه T است منتها به جای Logn ، رادیکال n داره. مشخصه که S از T کوچکتره (دقت شود که S به بعنوان تابع تبدیل برای T نیست)(S و T یکی نیستند و فرق دارند )
یعنی اگه بجای logn قرار بدیم رادیکال n:
با توجه به بزرگتر بودن رادیکال n نسبت به logn و اینکه این عبارت توی مخرجه، پس هر مرتبه ای بدست بیاد، از مرتبه‌ی رابطه‌ی اولیه کوچکتر خواهد بود( چون تقسیماتش کمتره درختش کوچکتر می شه) یعنی داریم:
[tex]T(n)=2T(\frac{n}{2}) T(\frac{n}{logn}) n>S(n)=2S(\frac{n}{2}) S(\frac{n}{\sqrt{n}}) n=2S(\frac{n}{2}) S(\sqrt{n}) n[/tex]
حالا برای حل (S(n داریم:
یک بار رابطه بازگشتی رو به صورت زیر در نظر می گیریم و مرتبه رو به دست میاریم.
[tex]S(n)= 2S(\frac{n}{2}) S(\frac{n}{2}) n=3S(\frac{n}{2}) n=O(n^{Log{_{2}}^{3}})[/tex]
یک بار دیگه رابطه بازگشتی رو به صورت زیر در نظر می گیریم و مرتبه رو به دست میاریم.
[tex]S(n)= 2S(\sqrt{n}) S(\sqrt{n}) n=3S(\sqrt{n}) n=O(n)[/tex]
مرتبه هر کدوم که بزرگتر بود میشه مرتبه رابطه بازگشتی اصلی (S(n یعنی:
[tex]S(n)=O(n^{{Log_{2}}^{3}})[/tex]
پس حد بالای S رو یافتیم.
حالا می تونیم مرتبه‌ی رابطه T رو نسبت به S بگیم.
طبق توضیحاتی که در اول پست دادم و نیز مرتبه‌ی S که بدستش آوردیم. داریم:
[tex]\begin{Bmatrix}T(n)> S(n) \\ S(n)=O(n^{Log{_{2}}^{3}}) \end{Bmatrix}\Rightarrow T(n)=\Omega(n^{Log{_{2}}^{3}})[/tex]
و این یک حد پایین برای رابطه‌ی T است.
اما حد بالا:
فرض می کنیم H تابعی است که مثل T هستش فقط به جای Logn در مخرج ۲ داره. مشخصه که H از T بزرگتره. داریم:
[tex]H(n)= 2H(\frac{n}{2}) H(\frac{n}{2}) n=3H(\frac{n}{2}) n=O(n^{Log{_{2}}^{3}})[/tex]
که این یک حد بالا برای T هستش چون H از T بزرگتره.
حد بالا و پایین مساوی شد.
پس طبق ساندویچ جواب نهایی می شه:
[tex]\Theta(n^{Log{_{2}}^{3}})[/tex]
اوکی؟
(۲۳ بهمن ۱۳۹۰ ۱۰:۲۸ ق.ظ)yaali نوشته شده توسط: یک بار رابطه بازگشتی رو به صورت زیر در نظر می گیریم و مرتبه رو به دست میاریم.
[tex]S(n)= 2S(\frac{n}{2}) S(\frac{n}{2}) n=3S(\frac{n}{2}) n=O(n^{Log{_{2}}^{3}})[/tex]
yaali جان چه لزومی داره که T رو به S تغییر نام میدی. S اصلا تابع تبدیل نیست فقط به قول شما یه اسم فرضی.
در واقع تابع S به خودی خود هیچ کاری اینجام نمیده.
مسئله بعد اینکه شما اومدی بجای مقادیر داخل پرانتز S یکبار [tex]\sqrt{n}[/tex] قرار دادی و یکبار [tex]\frac{n}{2}[/tex] و بعد اومدی حده پایینو بیگ اوی مقدار ماکزیمم این دوتا قرار دادی.
ولی وقتی دفعه اول مقدار [tex]\frac{n}{2}[/tex] رو در پرانتز های S قرار میدی باید توجه کنی که از رابطه اولیمون که مخرجش logn هست بزرگتر نباشه (چون در واقع S همون T هستش فرقی که نکرده). در این صورت میتونین ماکزیمم دو مقدارو به عنوان حده پایین رابطه اولیه قرار بدین اما اینجا مقداره S اولی رو که با مقدار [tex]\frac{n}{2}[/tex] دادن حل کردین ازمقدار مجانبی تابع اولیه ما هم جلو زده.(حده پایین و بالای ارسال قبلیمو نگاه کنین).
توجه داشته باشین که S به خودی خود هیچکاری انجام نمیده و فقط اسم تابع رو عوض کرده. که اصلا لزومی نداره اسمو عوض کنین. شما با همون نام T مقداره حده پایین و بالاشو حساب کنین مشکل حل میشه .
حد بالا
[tex]t(n)=2t(n/2) t(n/logn) n\Rightarrow s(n)=st(n/2) s(n/2) n [/tex]
[tex]t(n)=o(log_{2}^{3})[/tex]
حد پایین
[tex]t(n)=2t(n/2) t(n/logn) n\Rightarrow s(n)=2s(n/logn) s(n/logn) n\Rightarrow s(n)=3s(n/logn) n \Rightarrow h(n)=3h(n/\sqrt{n}) n\Rightarrow h(m)=\Omega(n)[/tex]
و
[tex]t(n)=\Omega s(n)[/tex]
(۱۷ بهمن ۱۳۹۰ ۱۱:۰۹ ب.ظ)mfXpert نوشته شده توسط: یک بار رابطه بازگشتی رو به صورت زیر در نظر بگیرید و مرتبه رو به دست بیارید.
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) n[/tex]
یک بار دیگه رابطه بازگشتی رو به صورت زیر در نظر بگیرید و مرتبه رو به دست بیارید.
[tex]T(n)=T(\sqrt{n}) T(\sqrt{n}) n[/tex]
مرتبه هر کدوم که بزرگتر بود میشه مرتبه رابطه بازگشتی اصلی
با این روش میشه کران بالا و پایینشو بدست آورد.
و مشخصه کران بالا همیشه بزرگتره.
[tex]T(n)=T (\frac{n}{\sqrt{n}}) T(\frac{n}{\sqrt{n}}) n=T(n)=T (\sqrt{n}) T(\sqrt{n}) n=O(n)< T(n)=T(\frac{n}{2}) T(\frac{n}{\sqrt{n}}) n<T(n)=T(\frac{n}{2}) T(\frac{n}{2}) n=O(nlogn) [/tex]
پس جواب بین n و nlogn هست.