سلام
دوستان
مرتبه زمانی این تابع چقدر؟
[tex]T(n)=T(\frac{n}{3})T(\frac{2n}{3}) n^{2}[/tex]
گزینه درست [tex]n^{2}[/tex]
و از طریق درخت بازگشت حلش کرده
ولی طبق نکته ای که من قبلا خونده بودم و این سوال مدرسان هم ذکر کرده
مرتبه زمانی باید [tex]n^{2}\log n[/tex]
باشه
ممنون میشم توضیح بدید
منم فکر میکنم هر ۲ رابطه (ی کتاب و اینی که شما گفتید) با مرتبه [tex]n^2[/tex] میشن . با قصیه آکرابازی میشه اینو اثبات کرد.
قضیه اینه که اگر رابطه ما به صورت [tex]T(n)=\sum_{i=0}^{k} (a_{i}T(b_{i} * n)) g(n)[/tex] بود جواب رابطه میشه :
[tex]T(n)= \Theta (n^p * (1 \int_{1}^{n} \frac{g(n)}{n^{p 1}}dn ))[/tex]
که p باید عددی انتخاب بشه که رابطه [tex]\sum _{i=0}^{k}a_{i} * b_{i}^{\ p} =1[/tex] درست باشه(a0=a1=1 , b0=1/3 ,b1=2/3) که ما در این مثال pمون برابر ۱میشه و [tex]g(n)[/tex] برابر [tex]n^2[/tex]ست.
خوب پس جواب میشه :
[tex]T(n)= \Theta (n^1 * (1 \int_{1}^{n} \frac{n^2}{n^{1 1}}dn ))[/tex] که بازم این میشه
[tex]T(n)= \Theta (n * (1 \int_{1}^{n} 1 dn ))[/tex] که انتگرال برابر میشه با
[tex]n |_{1}^{n}= n-1[/tex]و با قرار دادن این داخل اون معادله اصلی همون جوابی به دست میاد که ما دنبالش بودیم:
[tex]T(n)= \Theta (n * (1 n-1))[/tex] که بازم میشه [tex]T(n)= \Theta (n * (n))[/tex] که این همون [tex]T(n)= \Theta (n^2))[/tex] ست.
موفق باشید.
دوستان جواب رو با درخت بازگشت هم پیوست کردم
درخت بازگشت که به نظر درست میاد
(۲۲ دى ۱۳۹۱ ۰۶:۰۵ ب.ظ)Masoud05 نوشته شده توسط: شما از هر طریقی برید همون گزینه [tex]n^2 . log n[/tex] می رسید . این همون تعمیم قضیه اصلی هست . از روش درخت بازگشت ، جایگذاری با تکرار و ... هم حل میشه اما بهترین روشی همینی هست که خودتون گذاشتید . هیچ وقت برای این سوالات از روش تکرار و در خت بازگشت استفاده نکنید چون برای سوالات این شکلی فرمول کلی هست که هم سریع تر هست و هم احتمال اشتباه تون رو کم میکنهمسعود جان مطئنی؟!چه جوری با تعمیم مستر حل کردی؟!
من این فرمول کلی رو تا حالا ندیدم!و طبق اطلاعات خودم و CLRS حساب کردم شد همون n^2
تکلیف چیه؟!
این فرمول رو از کجا آورده!؟
این هم یه مثال مشابه:
Sent from my Google Galaxy Nexus using Tapatalk 2.4
(۲۲ دى ۱۳۹۱ ۰۶:۰۵ ب.ظ)Masoud05 نوشته شده توسط:بازم سلام من مجبور شدم بخاطر این فرمایش شما یه روش قابل فهم تر رو پیشنهاد کنم.(22 دى ۱۳۹۱ ۰۵:۳۴ ب.ظ)nina69 نوشته شده توسط: سلام
دوستان
مرتبه زمانی این تابع چقدر؟
۱- T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+n^{2}
گزینه درست n^{2}و از طریق درخت بازگشت حلش کرده
ولی طبق نکته ای که من قبلا خونده بودم و این سوال مدرسان هم ذکر کرده
مرتبه زمانی باید n^{2}\log nباشه
ممنون میشم توضیح بدید
شما از هر طریقی برید همون گزینه [tex]n^2 . log n[/tex] می رسید . این همون تعمیم قضیه اصلی هست . از روش درخت بازگشت ، جایگذاری با تکرار و ... هم حل میشه اما بهترین روشی همینی هست که خودتون گذاشتید . هیچ وقت برای این سوالات از روش تکرار و در خت بازگشت استفاده نکنید چون برای سوالات این شکلی فرمول کلی هست که هم سریع تر هست و هم احتمال اشتباه تون رو کم میکنه
ما تابع حداکثر رو حساب میکنیم. یعنی بالاترین حالت ممکن رو در نظر میگیریم.
از اونجا که [tex]\frac{2}{3}[/tex] دیرتر از [tex]\frac{1}{3}[/tex] کوچیک میشه پس حداکثر اینه که ما هر دو تا رو [tex]\frac{2}{3}[/tex] در نظر بگیریم. خوب رابطه شد :
[tex]T(n)= 2T(\frac{2n}{3}) n^2[/tex]
خوب حل این رابطه از طریق مستر که دیگه تابلوست که میشه [tex]O(n^2)[/tex] . در واقع جوابی که شما و کتاب میدید([tex]O(n^2lgn)[/tex] ) از حداکثر این تابع بیشتره ، من نمیدونم چرا شما انقدر با اطمینان این حرف رو زدید. خواهش میکنم استدلال بفرمایید
(۲۲ دى ۱۳۹۱ ۰۹:۵۰ ب.ظ)javadem نوشته شده توسط: خوب حل این رابطه از طریق مستر که دیگه تابلوست که میشه [tex]O(n^2)[/tex] . در واقع جوابی که شما و کتاب میدید([tex]O(n^2lgn)[/tex] ) از حداکثر این تابع بیشتره ، من نمیدونم چرا شما انقدر با اطمینان این حرف رو زدید. خواهش میکنم استدلال بفرماییدجواد جان من هم با شما موافقم!
(۲۲ دى ۱۳۹۱ ۰۹:۴۹ ب.ظ)Amir V نوشته شده توسط: این هم یه مثال مشابه:امیر این قضیش فرق می کنه به نظر من چون اخرش n داره نه n^2! وجوابشم درسته !
قضیه اش چه فرقی داره؟
اون اخرش فقط فرق داره!
Sent from my Google Galaxy Nexus using Tapatalk 2.4
من الان درختش رو رسم کردم . بله درسته من اشتباه نوشتم ، این اصلا تعمیم قضیه اصلی نبود . من به n , n^2 دقت نکرده بودم
اگه درختش رو رسم کنید و هزینه هر سطح رو با هم جمع کنید دارید :
[tex]T(n)=n^2 (5/9)^1 * n^2 (5/9)^2 * n^2 ... T(1)[/tex]
یعنی انقدر ادامه میدهیم که به شرایط مرزی برسیم ( طولانی ترین مسیر هم که مشخص کدوم هست )
حالا با یک فاکتور گیری داریم :
[tex]n^2 (1 (5/9) (5/9)^2 ...)= n^2 * T(1)[/tex]
تو کتاب آقای مقسمی یه فرمول اومده که میاد ضرایب T رو جمع میکنه که یا با قضیه اصلی یا تعمیمش میشه جواب نهایی رو بدست آورد. در نهایت همون [tex]n^2[/tex] درسته .
بهتره اصلا برای تست های خوش فرم اینجوری سراغ روش درخت بازگشت نرید و از همون فرمول های متداول استفاده کنید . فقط بی دقتی نکنید مثل من
ممنون از آقا جواد ( ارسال قبلیم رو حذف میکنم )
دوستان جواب n^2 اشتباهه جواب همون n^2.logn میشه چرا ارتفاع درخت رو در نظر نمیگیرید
اولا نمیدونم چرا فرمولی که نینا گذاشتن با اون فرمولی که توی عکس هست متفاوته
ولی واسه هر دو با حساب ارتفاع درخت همون n^2.logn میشه
ارتفاع درخت واسه اونی که عکسش گذاشتین logn در پایه ۴/۳ میشه ومقدار سطح ها هم از مرتیه n^2
البته دکتر قدسی هم این سوال رو حل کردن وجوابشون همینه.
(۱۳ بهمن ۱۳۹۱ ۰۸:۵۳ ب.ظ)maryam.raz نوشته شده توسط: دوستان جواب n^2 اشتباهه جواب همون n^2.logn میشه چرا ارتفاع درخت رو در نظر نمیگیرید
اولا نمیدونم چرا فرمولی که نینا گذاشتن با اون فرمولی که توی عکس هست متفاوته
ولی واسه هر دو با حساب ارتفاع درخت همون n^2.logn میشه
ارتفاع درخت واسه اونی که عکسش گذاشتین logn در پایه ۴/۳ میشه ومقدار سطح ها هم از مرتیه n^2
البته دکتر قدسی هم این سوال رو حل کردن وجوابشون همینه.
میشه بیشترتوضیح بدین ؟؟؟؟
(۱۳ بهمن ۱۳۹۱ ۰۸:۵۳ ب.ظ)maryam.raz نوشته شده توسط: دوستان جواب n^2 اشتباهه جواب همون n^2.logn میشه چرا ارتفاع درخت رو در نظر نمیگیرید
اولا نمیدونم چرا فرمولی که نینا گذاشتن با اون فرمولی که توی عکس هست متفاوته
ولی واسه هر دو با حساب ارتفاع درخت همون n^2.logn میشه
ارتفاع درخت واسه اونی که عکسش گذاشتین logn در پایه ۴/۳ میشه ومقدار سطح ها هم از مرتیه n^2
البته دکتر قدسی هم این سوال رو حل کردن وجوابشون همینه.
فرق عکس با اون فرمولی که نینا خانم گذاشتن مثل فرق دو تابع زیر هست :
[tex]2T(\frac{n}{2}) n = \Theta (nlgn)[/tex]
و
[tex]2T(\frac{n}{2}) n^2 = \Theta (n^2)[/tex]
که این تساوی ها از طریق مستر قابل اثباته!
این که دیگه خیلی مقدماتیه دکتر قدسی هم انسان هستند و قابلیت اشتباه دارند.
عدم توانایی بالای درخت بازگشت توی اثبات دقیق توابع بازگشتی که دیگه از کسی پوشیده نیست ، نمیدونم چرا اکثر دوستان سعی در اثبات روابط با این روش دارند؟؟؟؟
ببین، نکتش به صورت ساده میشه این:
اگر ضرایب n داخل فراخوانی‌ها جمعشون یک شد، شما حاصل کل عبارت به ازای قضیه‌ی مستر رو n بگیر!
حالا اینجا داریم [tex]f(n)=n^2[/tex]. خب حالا n بزرگتره یا [tex]n^2[/tex]؟ واضحه که [tex]n^2[/tex] بزرگتره و طبق مستر پاسخ میشه از [tex]O(n^2)[/tex].
توی پرانتز هر چی باشه فقط توان بزرگتر رو می گیریم.
هر t(n اردرش میشه lgn
خیلی هم ادامه پیدا کنه میشه order_n
اما سمت راست میشه n^2
----
شما نکته ی master رو درست خوندید اما فکر می کردید که سمت چپ هم n^2 شده و سپس سمت راست رو به اشتباه در lgn ضرب می کردید
---
javadem هم توی توضیح ترکوند و رابطه ی کامل ریاضیشو آورد.
امیدوارم موفق باشید.