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

مرتبه اجرایی تابع بازگشتی

ارسال:
  

khavar_1365 پرسیده:

مرتبه اجرایی تابع بازگشتی

سلام دوستان:میخواستم بدونم مرتبه اجرایی این تابع چی میشه؟!من خودم فکر میکنم
از مرتبه nمیشه اما داخل کتاب آقای مقسمی اونو۲به توانnبدست آوورده!!!!!اگر جواب درست اینه.لطف کنید نکته‌ها وراه حل اونهم بفرمایید.
باتشکر از همه شما
[[tex]t(n)=t(n-1)*t(n-1)[/tex]

۰
ارسال:
  

summer_66 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

(۱۴ مهر ۱۳۹۰ ۱۰:۴۷ ق.ظ)khavar_1365 نوشته شده توسط:  سلام دوستان:میخواستم بدونم مرتبه اجرایی این تابع چی میشه؟!من خودم فکر میکنم
از مرتبه nمیشه اما داخل کتاب آقای مقسمی اونو۲به توانnبدست آوورده!!!!!اگر جواب درست اینه.لطف کنید نکته‌ها وراه حل اونهم بفرمایید.
باتشکر از همه شما
[[tex]t(n)=t(n-1)*t(n-1)[/tex]
ببینید شما یه درخت به ارتفاع n خواهید داشت که هر کدام از نود های اون یک مرحله اجرای تابع هست که باید در محاسبه مرتبه اجرایی به حساب بیاد پس باید تعداد کل نود های این درخت به ارتفاع n رو بدست بیارید که میشه [tex]2^{n} -1[/tex] پس مرتبه اجرایی همون [tex]2^{n}[/tex] هست .شکلش رو بکشید تا متوجه بشید اگه موضوع براتون روشن نشد بگید تا شکلش رو بکشم.

۰
ارسال:
  

mfXpert پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

اگر تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] تو گسسته مطرح میشد و از شما خواسته میشد که جواب غیر بازگشتی تابع رو به دست بیارید اونوقت باید از روش های معمول حل روابط بازگشتی استفاده می کردید و جواب رو به دست می آوردید.اما چون تو بحث ساختمان و مرتبه اجرایی به دنبال تعداد کل فراخوانی های تابع t هستیم پس می تونیم علامت ضرب موجود در صورت سوال رو به جمع تبدیل کنیم.یعنی تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] رو به صورت [tex]t(n)=t(n-1) t(n-1)=2t(n-1)[/tex] در نظر بگیریم .حالا میتونیم با روش جایگذاری‌، تعداد فراخوانی های t رو به دست بیاریم:
[tex]t(n)=2t(n-1)[/tex]
[tex]t(n)=2(2t(n-2))[/tex]
.
.
.
[tex]t(n)=2^{n-1}(t(1))[/tex]

همونطور که مشخصه تابع بازگشتی از مرتبه دو به توان n هستش

ارسال:
  

khavar_1365 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

(۱۴ مهر ۱۳۹۰ ۰۲:۱۴ ب.ظ)mfXpert نوشته شده توسط:  اگر تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] تو گسسته مطرح میشد و از شما خواسته میشد که جواب غیر بازگشتی تابع رو به دست بیارید اونوقت باید از روش های معمول حل روابط بازگشتی استفاده می کردید و جواب رو به دست می آوردید.اما چون تو بحث ساختمان و مرتبه اجرایی به دنبال تعداد کل فراخوانی های تابع t هستیم پس می تونیم علامت ضرب موجود در صورت سوال رو به جمع تبدیل کنیم.یعنی تابع [tex]t(n)=t(n-1)*t(n-1)[/tex] رو به صورت [tex]t(n)=t(n-1) t(n-1)=2t(n-1)[/tex] در نظر بگیریم .حالا میتونیم با روش جایگذاری‌، تعداد فراخوانی های t رو به دست بیاریم:
[tex]t(n)=2t(n-1)[/tex]
[tex]t(n)=2(2t(n-2))[/tex]
.
.
.
[tex]t(n)=2^{n-1}(t(1))[/tex]

همونطور که مشخصه تابع بازگشتی از مرتبه دو به توان n هستش
سلام دوست عزیز
نکته بسیارخوب و مفیدی برای حل تستی اینگونه روابط بیان کردی بسیارمتشکرم.


(۱۴ مهر ۱۳۹۰ ۰۱:۳۰ ب.ظ)summer_66 نوشته شده توسط:  
(14 مهر ۱۳۹۰ ۱۰:۴۷ ق.ظ)khavar_1365 نوشته شده توسط:  سلام دوستان:میخواستم بدونم مرتبه اجرایی این تابع چی میشه؟!من خودم فکر میکنم
از مرتبه nمیشه اما داخل کتاب آقای مقسمی اونو۲به توانnبدست آوورده!!!!!اگر جواب درست اینه.لطف کنید نکته‌ها وراه حل اونهم بفرمایید.
باتشکر از همه شما
[[tex]t(n)=t(n-1)*t(n-1)[/tex]
ببینید شما یه درخت به ارتفاع n خواهید داشت که هر کدام از نود های اون یک مرحله اجرای تابع هست که باید در محاسبه مرتبه اجرایی به حساب بیاد پس باید تعداد کل نود های این درخت به ارتفاع n رو بدست بیارید که میشه [tex]2^{n} -1[/tex] پس مرتبه اجرایی همون [tex]2^{n}[/tex] هست .شکلش رو بکشید تا متوجه بشید اگه موضوع براتون روشن نشد بگید تا شکلش رو بکشم.

سلام واقعا از جوابتون ممنون.اگه لطف کنید و شکلش رو هم بکشید بسیار ممنون میشم جون برای رسم و حل روابط بازگشتی بادرخت هنوز مشکل دارم اگرنکته مفیدوکلی هست برای رسم با درخت بازگشتی حتما بیان کنید..ممنون
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

khavar_1365 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

سلام دوست عزیز.
بسیار سپاسگزارم از لطف و راهنماییتون.ممنون میشم اگه بیشتر از این بتونید تو حل اینجور مسایلی کمکم کنید بخصوص درخت بارگشتی.
با تشکر

ارسال:
  

summer_66 پاسخ داده:

RE: مرتبه اجرایی تابع بازگشتی

(۱۴ مهر ۱۳۹۰ ۱۰:۵۲ ب.ظ)khavar_1365 نوشته شده توسط:  سلام دوست عزیز.
بسیار سپاسگزارم از لطف و راهنماییتون.ممنون میشم اگه بیشتر از این بتونید تو حل اینجور مسایلی کمکم کنید بخصوص درخت بارگشتی.
با تشکر
اگه کمکی از دستم بربیاد در خدمت هستم.
درمورد روش دوم باید بگم روشم غیر آکادمیک بود و خوب نتونستم جمع و جورش کنم تا توضیح بدم پس فعلا منتظر روش دوم از طرف من نباشید تا ببینم میتونم سر راستش کنم برای بیان کردن یا نه.
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۳۹ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  تابع مولد ss311 ۰ ۱,۳۰۲ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۴۹ ب.ظ
آخرین ارسال: ss311
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۳۲ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۴۰۹ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۳,۲۸۴ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  مرتبه زمانی Sanazzz ۰ ۱,۸۲۹ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz
  درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) Saman ۶ ۶,۸۱۳ ۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ
آخرین ارسال: saeed_vahidi

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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