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

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

ارسال: #۲

۲۱ دى ۱۳۹۱, ۰۱:۱۹ ق.ظ

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

ارسال: #۴

۲۰ دى ۱۳۹۱, ۱۱:۲۸ ب.ظ

mfXpert پاسخ داده:

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

(۲۰ دى ۱۳۹۱ ۰۸:۰۱ ب.ظ)egm1176 نوشته شده توسط: لطفا بیشتر توضیح بدید.

$T(n)=T(n-3) \Theta (1) \leq T(n-1) \Theta (1)=\Theta (n)$

ارسال: #۵

۲۰ دى ۱۳۹۱, ۰۸:۰۱ ب.ظ

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
	زمان برگزاری کنکور ارشد ۹۸ به تعویق افتاد	elect	۲	۳,۲۱۹	۱۳ مهر ۱۳۹۸ ۰۵:۲۴ ب.ظ آخرین ارسال: saharfarhang
	محاسبه تراز معدل موثر از رشته آی تی یا علوم کامپیوتر به مهندسی کامپیوتر یا بالعکس	gnulinux	۰	۲,۶۳۶	۲۱ شهریور ۱۳۹۸ ۰۸:۳۷ ق.ظ آخرین ارسال: gnulinux

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

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

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

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

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

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

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

Can I see some ID?

Feeling left out?

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

Feeling left out?