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

محاسبه زمان اجرای الگوریتم بازگشتی

ارسال:
  

A.nonymous پرسیده:

محاسبه زمان اجرای الگوریتم بازگشتی

با توجه به تابع بازگشتی زیر مرتبه زمان را بیابید:

[تصویر:  153086_1_1379086621.png]

۱
ارسال:
  

Masoud05 پاسخ داده:

RE: محاسبه زمان اجرای الگوریتم بازگشتی

این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره

در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .

ارسال:
  

mosaferkuchulu پاسخ داده:

RE: محاسبه زمان اجرای الگوریتم بازگشتی

(۲۱ دى ۱۳۹۱ ۰۱:۱۹ ق.ظ)Masoud05 نوشته شده توسط:  این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره

در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .

بله من دقیقا همون اشتباه و کردم.بعد که بچه ها تذکر دادن و دوباره نگاه کردم متوجه شدم.
ممنون از توضیحاتتون.
این نشون دهنده ی اهمیت دقت در موفقیته Big Grin Big Grin
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

mfXpert پاسخ داده:

RE: محاسبه زمان اجرای الگوریتم بازگشتی

(۲۰ دى ۱۳۹۱ ۰۸:۰۱ ب.ظ)egm1176 نوشته شده توسط:  لطفا بیشتر توضیح بدید.
[tex]T(n)=T(n-3) \Theta (1) \leq T(n-1) \Theta (1)=\Theta (n)[/tex]

۱
ارسال:
  

egm1176 پاسخ داده:

محاسبه زمان اجرای الگوریتم بازگشتی

لطفا بیشتر توضیح بدید.

۰
ارسال:
  

۸Operation پاسخ داده:

محاسبه زمان اجرای الگوریتم بازگشتی

(۱۹ دى ۱۳۹۱ ۱۱:۲۸ ب.ظ)nazaninzahra2 نوشته شده توسط:  میشه : O(n)
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.
موافقم
مشاهده‌ی وب‌سایت کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۴ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۴۷۳ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۲,۵۹۴ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  اجرای نرم افزار ویندوز در اندروید elecomco ۰ ۲,۷۸۶ ۰۴ خرداد ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: elecomco
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  یادگیری برنامه نویسی تا اجرای پروژه های بزرگ The BesT ۳ ۳,۲۳۴ ۱۲ آذر ۱۳۹۸ ۰۳:۵۸ ب.ظ
آخرین ارسال: marvelous
  نحوه محاسبه دفیق لگاریتم بدون ماشین حساب mcse2010 ۲ ۷۹,۸۶۰ ۲۸ مهر ۱۳۹۸ ۰۹:۳۸ ق.ظ
آخرین ارسال: chemical_darton29
Exclamation زمان برگزاری کنکور ارشد ۹۸ به تعویق افتاد elect ۲ ۲,۶۳۸ ۱۳ مهر ۱۳۹۸ ۰۵:۲۴ ب.ظ
آخرین ارسال: saharfarhang
  محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس gnulinux ۰ ۲,۲۷۴ ۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ
آخرین ارسال: gnulinux

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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