زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۱:۰۵ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال، مرتبه اجرایی و گام برنامه

ارسال:
  

Mr.R3ZA پرسیده:

Question سوال، مرتبه اجرایی و گام برنامه

با سلام و عرض خسته نباشید.

سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.



سوال دوم) با توجه به عکس زیر چرا گام برنامه شده nm و تعداد تکرار دستور اصلی شده n ؟؟؟
به نظر من بایستی گام برنامه ۲nm+2n+1 و تعداد تکرار دستور اصلی nm میشد.



لطفا راهنمایی و نظر بدید.
با تشکر.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

boshbosh پاسخ داده:

RE: سوال، مرتبه اجرایی و گام برنامه

(۲۸ تیر ۱۳۹۶ ۱۲:۰۹ ب.ظ)Mr.R3ZA نوشته شده توسط:  با سلام و عرض خسته نباشید.

سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.


سوال دوم) با توجه به عکس زیر چرا گام برنامه شده nm و تعداد تکرار دستور اصلی شده n ؟؟؟
به نظر من بایستی گام برنامه ۲nm+2n+1 و تعداد تکرار دستور اصلی nm میشد.


لطفا راهنمایی و نظر بدید.
با تشکر.
سوال ۱ : مرتبه از قضیه master حساب میشه. مرتبه اجرایی که n میشه منظور (O(n است. که میتونه هر ضریب ثابتی داشته باشه. ولی ضریبشو نمینویسن دیگه. مثلا ۱۰n ۱۰۰n هم مرتبه هستن چون ضریب ثابت بی تاثیره

سوال ۲: منظورتو از گام نفهمیدم اما اگه n و m متغیر هستن مرتبه از (O(nm است. تعداد اجرا دستور اصلی mn است.گام اگه منظورت تعداد دقیق اجراس میشه : ۱+(n(m+1
حلقه داخلی m بار اجرا میشه یک بار آخر اجرا میشه که شرط حلقه رد میشه و از for میاد بیرون. برای حلقه n هم همینجوره


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

ارسال:
  

Mr.R3ZA پاسخ داده:

RE: سوال، مرتبه اجرایی و گام برنامه

[/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 بار
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

boshbosh پاسخ داده:

RE: سوال، مرتبه اجرایی و گام برنامه

سوال ۲: منظورتو از گام نفهمیدم اما اگه 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]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

msour44 پاسخ داده:

RE: سوال، مرتبه اجرایی و گام برنامه

(۲۹ تیر ۱۳۹۶ ۰۹:۵۱ ق.ظ)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]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Mr.R3ZA پاسخ داده:

RE: سوال، مرتبه اجرایی و گام برنامه

(۲۸ تیر ۱۳۹۶ ۱۲:۴۳ ب.ظ)boshbosh نوشته شده توسط:  
(28 تیر ۱۳۹۶ ۱۲:۰۹ ب.ظ)Mr.R3ZA نوشته شده توسط:  با سلام و عرض خسته نباشید.

سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.
سوال ۱ : مرتبه از قضیه master حساب میشه. مرتبه اجرایی که n میشه منظور (O(n است. که میتونه هر ضریب ثابتی داشته باشه. ولی ضریبشو نمینویسن دیگه. مثلا ۱۰n ۱۰۰n هم مرتبه هستن چون ضریب ثابت بی تاثیره

دوست عزیز فکر کنم قضیه Master برای زمانی که a=b است، بصورت nlogn است. این سوال از قضیه Master حل نمیشه.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

mino0z پاسخ داده:

RE: سوال، مرتبه اجرایی و گام برنامه

(۲۸ تیر ۱۳۹۶ ۱۲:۰۹ ب.ظ)Mr.R3ZA نوشته شده توسط:  با سلام و عرض خسته نباشید.

سوال اول) با توجه به عکس زیر چرا مرتبه میشه n. مگه مرتبه اجرایی به اندازه تعداد فراخوانی های درخت بازگشتی نیست (یعنی تعداد گره ها، که در اینجا ۱۵ است)؟؟ مثل فاکتوریل که تعداد فراخوانی ها (و یا گره های درخت بازگشتی) به اندازه n است و مرتبه آن را n میکند.

این سوال که به روش درختی حل شده است کاملا واضح است که ما n تا t(1) داریم ولی روش دیگه به روش master theorem است ۲t(n/2) و وb=2 و a=2 جواب بدست می آید
سوال دوم) با توجه به عکس زیر چرا گام برنامه شده nm و تعداد تکرار دستور اصلی شده n ؟؟؟
به نظر من بایستی گام برنامه ۲nm+2n+1 و تعداد تکرار دستور اصلی nm میشد.


لطفا راهنمایی و نظر بدید.
با تشکر.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کمک برای شروع برنامه نویسی seyed ehsn ۲۱ ۱۴,۰۶۱ ۲۴ بهمن ۱۴۰۲ ۰۵:۱۰ ب.ظ
آخرین ارسال: maryamjafari63
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۴۱ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  رودمپی برای برنامه نویسی Doctorwho ۱ ۱,۷۴۵ ۲۵ آذر ۱۴۰۰ ۰۳:۰۲ ق.ظ
آخرین ارسال: one hacker alone
  استخدام برنامه نویس یا کارآموز برنامه نویسی سی شارپ Hesitant_Girl ۰ ۱,۴۵۷ ۲۰ شهریور ۱۴۰۰ ۱۲:۰۲ ب.ظ
آخرین ارسال: Hesitant_Girl
  رودمپی برای یادگیری برنامه نویسی Doctorwho ۰ ۱,۵۴۱ ۲۳ اردیبهشت ۱۴۰۰ ۱۱:۲۲ ق.ظ
آخرین ارسال: Doctorwho
  درخواست برنامه برای اردینو در iot seokheiry ۱ ۲,۹۵۲ ۱۳ بهمن ۱۳۹۹ ۱۲:۵۵ ب.ظ
آخرین ارسال: iot-programer
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
Lightbulb گام به گام تا ارشد ۹۹ marvelous ۴۹۲ ۱۷۳,۵۲۵ ۱۵ شهریور ۱۳۹۹ ۰۷:۴۸ ب.ظ
آخرین ارسال: شانی
  کدام زبان برنامه‌نویسی بهترین انتخاب است؟ elecomco ۲ ۲,۷۳۴ ۱۰ شهریور ۱۳۹۹ ۰۵:۱۶ ب.ظ
آخرین ارسال: kilookiloo

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close