با سلام و عرض خسته نباشید.
سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.
[attachment=21995]
سوال دوم) با توجه به عکس زیر چرا گام برنامه شده nm و تعداد تکرار دستور اصلی شده n ؟؟؟
به نظر من بایستی گام برنامه ۲nm+2n+1 و تعداد تکرار دستور اصلی nm میشد.
[attachment=21996]
لطفا راهنمایی و نظر بدید.
با تشکر.
(۲۸ تیر ۱۳۹۶ ۱۲:۰۹ ب.ظ)Mr.R3ZA نوشته شده توسط: با سلام و عرض خسته نباشید.سوال ۱ : مرتبه از قضیه master حساب میشه. مرتبه اجرایی که n میشه منظور (O(n است. که میتونه هر ضریب ثابتی داشته باشه. ولی ضریبشو نمینویسن دیگه. مثلا ۱۰n ۱۰۰n هم مرتبه هستن چون ضریب ثابت بی تاثیره
سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.
سوال دوم) با توجه به عکس زیر چرا گام برنامه شده nm و تعداد تکرار دستور اصلی شده n ؟؟؟
به نظر من بایستی گام برنامه ۲nm+2n+1 و تعداد تکرار دستور اصلی nm میشد.
لطفا راهنمایی و نظر بدید.
با تشکر.
سوال ۲: منظورتو از گام نفهمیدم اما اگه n و m متغیر هستن مرتبه از (O(nm است. تعداد اجرا دستور اصلی mn است.گام اگه منظورت تعداد دقیق اجراس میشه : ۱+(n(m+1
حلقه داخلی m بار اجرا میشه یک بار آخر اجرا میشه که شرط حلقه رد میشه و از for میاد بیرون. برای حلقه n هم همینجوره
[/quote]
سوال ۲: منظورتو از گام نفهمیدم اما اگه n و m متغیر هستن مرتبه از (O(nm است. تعداد اجرا دستور اصلی mn است.گام اگه منظورت تعداد دقیق اجراس میشه : ۱+(n(m+1
حلقه داخلی m بار اجرا میشه یک بار آخر اجرا میشه که شرط حلقه رد میشه و از for میاد بیرون. برای حلقه n هم همینجوره
[/quote]
منظورم از گام، همون تعداد دقیق اجراست. (یعنی تمام مراحل)
چرا ۱+(n(m+1 میشه؟؟!! بنظرم اشتباس!!!
۲nm+2n+1 میشه، چون دستور حلقه درونی mبار میچرخه و خود حلقه درونی هم m+1 بار.حالا اینا خودشون دستورات حلقه بیرونی محسوب میشن که nبار میچرخن و خود حلقه بیرونی هم n+1 بار
سوال ۲: منظورتو از گام نفهمیدم اما اگه n و m متغیر هستن مرتبه از (O(nm است. تعداد اجرا دستور اصلی mn است.گام اگه منظورت تعداد دقیق اجراس میشه : ۱+(n(m+1
حلقه داخلی m بار اجرا میشه یک بار آخر اجرا میشه که شرط حلقه رد میشه و از for میاد بیرون. برای حلقه n هم همینجوره
[/quote]
منظورم از گام، همون تعداد دقیق اجراست. (یعنی تمام مراحل)
چرا ۱+(n(m+1 میشه؟؟!! بنظرم اشتباس!!!
۲nm+2n+1 میشه، چون دستور حلقه درونی mبار میچرخه و خود حلقه درونی هم m+1 بار.حالا اینا خودشون دستورات حلقه بیرونی محسوب میشن که nبار میچرخن و خود حلقه بیرونی هم n+1 بار
[/quote]
»ن تعداد اجرا خط به خط منظورم نبود فقط واسه حلقه ها بود. اگه خط به خط بخواهیذ دستور اصلی m بار. حلقه داخلی ۱+m بار مجموع ۱+۲m بار. ضرب در n برای حلقه خارجی. ۱ بار هم حلقه خارجی شرطش نقض میشه و دیگه توش نمیره. پس جواب کل :
[tex]((2m+1)\cdot n)+1[/tex]
(۲۹ تیر ۱۳۹۶ ۰۹:۵۱ ق.ظ)boshbosh نوشته شده توسط:با تشکر از پاسخ تان(28 تیر ۱۳۹۶ ۰۵:۲۰ ب.ظ)Mr.R3ZA نوشته شده توسط:
»ن تعداد اجرا خط به خط منظورم نبود فقط واسه حلقه ها بود. اگه خط به خط بخواهیذ دستور اصلی m بار. حلقه داخلی ۱+m بار مجموع ۱+۲m بار. ضرب در n برای حلقه خارجی. ۱ بار هم حلقه خارجی شرطش نقض میشه و دیگه توش نمیره. پس جواب کل :
[tex]((2m+1)\cdot n)+1[/tex]
ولی جواب۲nm+2n+1 میشه شما تعداد اجرای حلقه اول رو یک بار فرض کردید درحالی که n+1 بار خود حلقه اجرا میشه (بررسی شرط و افزودن گام)و n بار دستورات داخل حلقه. حلقه داخلی هم m+1 بار اجرا میشه و دستور داخل ان m بار ولی این دو با هر تکرار حلقه بیرونی محاسبه می شوند پس داریم
[tex]n(m+1+m)+n+1=2nm+2n+1[/tex]
(۲۸ تیر ۱۳۹۶ ۱۲:۴۳ ب.ظ)boshbosh نوشته شده توسط:(28 تیر ۱۳۹۶ ۱۲:۰۹ ب.ظ)Mr.R3ZA نوشته شده توسط: با سلام و عرض خسته نباشید.سوال ۱ : مرتبه از قضیه master حساب میشه. مرتبه اجرایی که n میشه منظور (O(n است. که میتونه هر ضریب ثابتی داشته باشه. ولی ضریبشو نمینویسن دیگه. مثلا ۱۰n ۱۰۰n هم مرتبه هستن چون ضریب ثابت بی تاثیره
سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.
دوست عزیز فکر کنم قضیه Master برای زمانی که a=b است، بصورت nlogn است. این سوال از قضیه Master حل نمیشه.
(۲۸ تیر ۱۳۹۶ ۱۲:۰۹ ب.ظ)Mr.R3ZA نوشته شده توسط: با سلام و عرض خسته نباشید.
سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.
این سوال که به روش درختی حل شده است کاملا واضح است که ما n تا t(1) داریم ولی روش دیگه به روش master theorem است ۲t(n/2) و وb=2 و a=2 جواب بدست می آید
سوال دوم) با توجه به عکس زیر چرا گام برنامه شده nm و تعداد تکرار دستور اصلی شده n ؟؟؟
به نظر من بایستی گام برنامه ۲nm+2n+1 و تعداد تکرار دستور اصلی nm میشد.
لطفا راهنمایی و نظر بدید.
با تشکر.