(۲۲ بهمن ۱۳۹۰ ۱۲:۲۶ ق.ظ)yaali نوشته شده توسط: فکر کنم ساندویچ نشه. چون من در بالا براش حد پایین بیگ اوی n رو بدست آوردم.
بله ممکنه دقیقا ساندویچ نشه.
شما برای کران پایین مقدار امگا n رو بدست اوردین.
پس جواب بین n و nlogn هستش.
آفرین
اما:
سوال خیلی عجیبیه
شما مخرج رو دادید ۲ شد nlogn حالا بدید ۴ ببینید چند می شه .
(۲۲ بهمن ۱۳۹۰ ۱۲:۳۱ ق.ظ)yaali نوشته شده توسط: آفرین
اما:
سوال خیلی عجیبیه
شما مخرج رو دادید ۲ شد nlogn حالا بدید ۴ ببینید چند می شه .
این به اصله موضوع آسیب نمیزنه.
شما دارین با بزرگتر کردن مخرج کران بالا رو محدودتر میکنین و به مقدار حقیقی نزدیکتر.
گفتم بین این دو مقداره ولی مقداره دقیقترش باید تحقیق بشه.
بله. ممنونم. درسته . اما
حالا شما بیا به جای ۲ بگیر ۱/۵ .
از nlogn حد بالاش داره می زنه بالا.
سوال خوش تیپیه
(۲۲ بهمن ۱۳۹۰ ۱۲:۵۱ ق.ظ)yaali نوشته شده توسط: بله. ممنونم. درسته . اما
حالا شما بیا به جای ۲ بگیر ۱/۵ .
از nlogn حد بالاش داره می زنه بالا.
سوال خوش تیپیه
خوب yaaliجان هرچی مخرجو کوچکتر بگیری مقدار مجانبی بالاتر میره و این تناقضی نداره.
شما اونجا که بجای ۲ مقداره ۴ رو گذاشتین مقداره مجانبی رو کمتر کردین و به سمت مقداره واقعی نزدیکتر.
حالا بجای ۲ مقداره ۱/۵ رو قرار دادین که دارین مقداره مجانبی رو بزرگتر میکنین و از مقداره حقیقی دورتر.
ممنون که وقت می گذاری
من می گم حد بالاش nlogn نیست. یک کمی بیشتره.
حد پایین چی؟ به نظرت پایین‌تر از n می ره؟
(۲۲ بهمن ۱۳۹۰ ۰۱:۰۲ ق.ظ)yaali نوشته شده توسط: ممنون که وقت می گذاریخواهش میکنم دوست عزیز.
من می گم حد بالاش nlogn نیست. یک کمی بیشتره.
حد پایین چی؟ به نظرت پایین‌تر از n می ره؟
حده بالاش صد در صد کمتر از nlogn هست.
حده پایینشم صد در صد بزرگتر از n هست.
در این دو مورد شکی نیست.
مثلا nlogloglogn. البته این مقدار نیست همینطوری گفتم که مقدارای احتمالیشو بدونین.
اگه توی محاسبه حد بالاش بگذاریم ۱/۵ اونوقت با مستر می شه n به توان لگاریتم دو در مبنای۱/۵ که از nLogn یک کمی بیشتره.
واقعا شرمنده شدم که وقتت رو اینقدر گرفتم.
(۲۲ بهمن ۱۳۹۰ ۰۱:۱۳ ق.ظ)yaali نوشته شده توسط: اگه توی محاسبه حد بالاش بگذاریم ۱/۵ اونوقت با مستر می شه n به توان لگاریتم دو در مبنای۱/۵ که از Logn یک کمی بیشتره.
واقعا شرمنده شدم که وقتت رو اینقدر گرفتم.
اکه از راه مستر برین میشه n به توانه یکو خرده ای. پس از (f(n بزرگتر میشه یعنی جوابو بدست میارین n به توانه یکو خرده ای که از nlogn بزرگتره.
گفتم مخرجو کم کنین کرانه بالا رو بزرگتر میکنین و به سمته مقداره غیر واقعیتری هدایت میشین.
[tex]T(n)=2T(\frac{n}{logn}) 3n< T(n)=2T(\frac{n}{4}) 3n<T(n)=2T(\frac{n}{2}) 3n=O(nlogn)< T(n)=2T(\frac{n}{1/5}) 3n=O(n^{1/...})[/tex]
متشکرم
تصویب شد:
جواب بین n و nLogn هستش.
ولی سوال جالبی بود.
(۲۲ بهمن ۱۳۹۰ ۰۱:۲۵ ق.ظ)yaali نوشته شده توسط: متشکرم
تصویب شد:
جواب بین n و nLogn هستش.
ولی سوال جالبی بود.
خواهش میکنم.
خدارو شکر
.بله سواله خوبی بود.
ممنون از شما بخاطره زحماتتون برای ارتقای علمی اعضای مانشت.
من در ارسال ۴ یک حد پایین براش پیدا کردم.
حالا اگه به جای Lognدر صورت سوال عدد ۲ رو قرار بدیم و مسئله رو حل کنیم داریم:
[tex]T(n)= 2T(\frac{n}{2}) T(\frac{n}{2}) n=3T(\frac{n}{2}) n=O(n^{Log{_{2}}^{3}})[/tex]
که یک حد بالا براش بدست آمد
و کاملا مشابه حد پایینشه.
پس طبق ساندویچ جواب نهایی می شه:
[tex]\Theta(n^{Log{_{2}}^{3}})[/tex]
کسی در مورد پاسخ من در ارسال ۴ و این پاسخ من نظری نداره؟
متشکرم.
شما در ارسال ۴ یه حده بالا براش پیدا کردین.
[tex]T(n)=2T(\frac{n}{2}) T(\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=3T(\frac{n}{2}) n=O(n^{Log{_{2}}^{3}})[/tex]
(۲۱ بهمن ۱۳۹۰ ۰۴:۰۶ ب.ظ)yaali نوشته شده توسط: ا
حالا برای حل (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]
اینجا با S همون حده بالا رو حساب کردین.
حده پایین:
[tex]T(n)=2T(\frac{n}{2}) T(\frac{n}{\sqrt{n}}) n[/tex]
با تغییر متغییر [tex]n=2^{m}[/tex] داریم:
[tex]T(2^{m})=2T(2^{m-1}) T(2^{\frac{m}{2}}) 2^{m}[/tex]
[tex]S(m)=2S(m-1) S(\frac{m}{2}) 2^{m} [/tex]
[tex]2S(m-1) S(\frac{m}{2}) 2^{m}>2S(\frac{m}{2}) S(\frac{m}{2}) 2^{m}=3S(\frac{m}{2}) 2^{m}=O(2^{m})=O(2^{logn})=O(n)[/tex]
پس جواب بین n و [tex]O(n^{Log{_{2}}^{3}})[/tex] هست.
متشکرم.
و اما استدلال من:
اولا رابطه اصلی و مورد نظر T هستش نه S .
حد پایین T:
در ارسال ۴ من S را بعنوان رابطه ای که از T کوچکتره در نظر گرفتم.
بعد به روش خاصی که اونجا نوشته‌ام حد بالای S رو بدست آوردم.
و چون T>S هستش پس حد بالای S می شه حد پایین برای T .
در نتیجه در اون ارسال حد پایین برای T بدست آمد.
اما حد بالای T:
در ارسال ۱۱ به سادگی به دست آمد.
هر دو شد [tex]\Theta(n^{Log{_{2}}^{3}})[/tex] پس طبق ساندویچ جواب اصلی T همین می شه.
(۲۲ بهمن ۱۳۹۰ ۰۸:۲۵ ب.ظ)sasanlive نوشته شده توسط: اینجا با S همون حده بالا رو حساب کردین.بله. حد بالای S رو که می شه حد پایین T .
اون حد پایین که شما یافته‌اید در واقع حد پایین S هستش نه T .
و فکر می کنم که در اینجا نمی شه اون منهای یک رو بی خیال شد.
(۲۲ بهمن ۱۳۹۰ ۱۰:۰۲ ب.ظ)yaali نوشته شده توسط: اولا رابطه اصلی و مورد نظر T هستش نه S .
حد پایین T:
در ارسال ۴ من S را بعنوان رابطه ای که از T کوچکتره در نظر گرفتم.
بعد به روش خاصی که اونجا نوشته‌ام حد بالای S رو بدست آوردم.
و چون T>S هستش پس حد بالای S می شه حد پایین برای T .
در نتیجه در اون ارسال حد پایین برای T بدست آمد.
اما حد بالای T:
در ارسال ۱۱ به سادگی به دست آمد.
هر دو شد [tex]\Theta(n^{Log{_{2}}^{3}})[/tex] پس طبق ساندویچ جواب اصلی T همین می شه.
(۲۲ بهمن ۱۳۹۰ ۰۸:۲۵ ب.ظ)sasanlive نوشته شده توسط: اینجا با S همون حده بالا رو حساب کردین.بله. حد بالای S رو که می شه حد پایین T .
اون حد پایین که شما یافته‌اید در واقع حد پایین S هستش نه T .
و فکر می کنم که در اینجا نمی شه اون منهای یک رو بی خیال شد.
تابع S شما یه تابع تبدیل نیست.
شما فقط بجای T از S استفاده کردین و بجای logn مقدار رادیکال n رو قرار دادین.
دوباره اومدین یه بار بجای رادیکال n مقدار ۲ رو تو مخرج قرار دادین. یعنی همون حده بالای T رو بدست اوردین.