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

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

ارسال:
  

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 نوشته شده توسط:  سلام دوست عزیز.
بسیار سپاسگزارم از لطف و راهنماییتون.ممنون میشم اگه بیشتر از این بتونید تو حل اینجور مسایلی کمکم کنید بخصوص درخت بارگشتی.
با تشکر
اگه کمکی از دستم بربیاد در خدمت هستم.
درمورد روش دوم باید بگم روشم غیر آکادمیک بود و خوب نتونستم جمع و جورش کنم تا توضیح بدم پس فعلا منتظر روش دوم از طرف من نباشید تا ببینم میتونم سر راستش کنم برای بیان کردن یا نه.
یافتن تمامی ارسال‌های این کاربر



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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