سلام دوستان
اگر ممکنه زودتر راهنماییم کنید
دو ارایه مرتب A , B با طول های m , n داده شده اند. میخواهیم با کمترین تعداد خواندن درایه های این دو ارایه .میانه m+n را بدست بیاوریم
رابطه بازگشتی که نحوه رفتار این الگوریتم را نشان می دهد؟
-------[/align]
دوستان خواهشا جواب سوال منو بدید . بین دو تا گزینه شک دارم
اگه بخوام خلاصه بگم کافی میانه هر ارایه را بدست بیاری n/2 یا m/2 بعدش جواب در یکی از این دو تا هست ولی هر دو نیست. و از اونجایی که ارایه ما مرتب هزینه بدست اوردن میانه یک هست.اون وقت هزینه (پیچیدگی ) اولی میشه logm و دومی logn جواب کلی (log(n+m
ممنونم از جوابتون
اما من رابطه بازگشتیش و تحلیلش را میخام .تو پاسخ تشریحی گفته گزینه ۴ و تستی گزینه ۲ را علامت زده.
اگه جواب بدید ممنون میشم
(۱۸ دى ۱۳۹۳ ۰۳:۴۷ ب.ظ)maryam.roshan نوشته شده توسط: ممنونم از جوابتون/۲
اما من رابطه بازگشتیش و تحلیلش را میخام .تو پاسخ تشریحی گفته گزینه ۴ و تستی گزینه ۲ را علامت زده.
اگه جواب بدید ممنون میشم
رابطه بازگشتی میشه ۱ + ( T(n/2 .m/2 که میانه هر دو ارایه بدست اوردیم بعدش با هزینه یک میانه ها را بدست اوردیم جواب طبق اصل سوم قضیه اصلی بدست میاد.جواب همونی که پاسخ تشریحی این سوال دو ارایه یکیش m و یکیش n داده هستش و فرقی داره وقتی دو ارایه هر دو n عنصر داشته باشن.روش همینه فقط به نوع ارایه و تعداد عناصر دقت کنید.
ببخشید گفتید اگر هردو ارایه n عضوی باشن رابطه بازگشتی چی میشه؟
جواب این سوال ۲+(T(n/2, m/2
در هر بار میانه هر کدوم از آرایه ها رو پیدا میکنیم مثلا اگه فرض کتیم میانه آرایه A از میانه آرایه B بزرگتره میانه کل آرایه در جایی بین این دو میانه س یعنی در نیمه بزرگتر از میانه B و در نیمه کوچکتر از میانه A چون هر دو آرایه مرتب هستند. و به همین طریق به صورت بازگشتی نیمی از هر دو آرایه در هر بار فراخوانی حذف میشه .
در هر بار فراخوانی یکبار باید میانه آرایه اولو محاسبه کنیم و یک بار میانه آرایه دوم پس هزینه هر بار اجرا میشه ۲
تو جواب سوال ۳۲ گفته
[tex]T(n)\:=T(n\:\backslash2)\: 1[/tex]
(۱۹ دى ۱۳۹۳ ۱۰:۳۳ ب.ظ)maryam.roshan نوشته شده توسط: تو جواب سوال ۳۲ گفتهجوابی که تو سوال ۳۲ دادن درسته در واقع توضیحش اینه که هر بار نصف اعدادو کنار میزاریم تو فرمول بالا هم ذاشتن (۱)O نه خود ۱، [tex]T(n)\: =T(n\: \backslash2)\: O(1)[/tex]
[tex]T(n)\: =T(n\: \backslash2)\: 1[/tex]
میمونه هزینه هر بار عمل که به نظر من دو میشه چون دو تا میانه باید پیدا کنیم ولی خوب تو محاسبه پیچیدی تفاوتی نمیکنه
درمورد اون سوال ۶۰ هم خود صورت سوال گفته فرض کنید ( T(n ,m بیشترین تعداد دسترسی و ما هر بار نصفی از هر آرایه رو کنار میذاریم بیشترین دسترسی میشه ( T(n/2,m/2 ولی بازم میگم هزینه هر اجرا میشه ۲
درسته .ممنونم ازتون
سوال سال ۸۷ هوش مصنوعی هم همین بود که پاسخش
[tex]T(2n)\: =T(n)\: 2[/tex]
بود.برای دو ارایه که تعداد اعناصر هرکدوم n بود