الله
می خواستم در مورد این نکته ظریف بپرسم که دقیقا تفاوت مرتبه(هزینه) اجرا بین دو تابع بازگشتی (f(n)=n+f(n-1 و (T(n)=n+T(n-1 چیست ؟
( در اولی می شه n و در دومی می شه n^2 )
متشکرم.
(۱۰ مهر ۱۳۹۰ ۰۶:۱۶ ب.ظ)yaali نوشته شده توسط: الله
می خواستم در مورد این نکته ظریف بپرسم که دقیقا تفاوت بین این دو چیست؟
مثلا در مورد تابع بازگشتی (f(n)=n+f(n-1 یا (T(n)=n+T(n-1 در جایی می خوندم که زمان اجرا n و مرتبه اجرا n^2 هستش.
همچنین درمورد تابع بازگشتی فاکتوریل که اگه زمان اجرا رو بخواهیم می شه n، چون n بار فراخوانی می شه اما اگه با روش جایگزینی مرتبه‌ی آن را حساب کنیم
می شه n فاکتوریل.
اینکه در سوال از ما کدوم رو می خواهند از کجا بفهمیم؟
البته فکر کنم بیشتر جاها یکسان باشند.
نظر شما چیه؟
متشکرم.
دوست عزیز فکر کنم شما دارید کپی تست‌ها ساختمان رو مینویسید، اگه اینطوره باید بگم:
اونی که تابعش (f(nهست . این در واقع خود الگوریتم هست( خود شبه کد )پس اینجا برای مقدار n که توی رابطه هست زمانی نیاز نیست صرف بشه . اما اونی که (T(n هست برای خود مقدار n یعنی n عمل پس به زمان n نیاز داره. امیدورام متوجه منظورم شده باشه( f یه رابطه ساده هست مثل جمع اما T توی اینجا یه رابطه بازگشتی هست )
عین تست رو بزار تا برات بگم چی به چیه
متشکرم از راهنماییتون.
یعنی شما فقط از لفظ f یا T متوجه می شوید ؟
چون گاهی اصلا شبه کد را نداده و آمده رابطه بازگشتی را با حرف f نوشته.
و یا ممکنه شبه کد باشه ولی از حرف T استفاده کرده باشه !؟
(۱۰ مهر ۱۳۹۰ ۱۰:۱۷ ب.ظ)Masoud05 نوشته شده توسط: دوست عزیز فکر کنم شما دارید کپی تست‌ها ساختمان رو مینویسید، اگه اینطوره باید بگم:ببخشید متوجه این فرمایشتون نشدم !
(۱۰ مهر ۱۳۹۰ ۱۱:۰۰ ب.ظ)yaali نوشته شده توسط: متشکرم از راهنماییتون.
یعنی شما فقط از لفظ f یا T متوجه می شوید ؟
چون گاهی اصلا شبه کد را نداده و آمده رابطه بازگشتی را با حرف f نوشته.
و یا ممکنه شبه کد باشه ولی از حرف T استفاده کرده باشه !؟
(۱۰ مهر ۱۳۹۰ ۱۰:۱۷ ب.ظ)Masoud05 نوشته شده توسط: دوست عزیز فکر کنم شما دارید کپی تست‌ها ساختمان رو مینویسید، اگه اینطوره باید بگم:ببخشید متوجه این فرمایشتون نشدم !
نه . ۲ تا تست ساختمان هست که عین همه فقط یکش تابع هست و یکیش رابطه بازگشتی( تنها فرقشون توی همین کلمه هست )اویل رو با f نشون داده اونجا و دومی رو با T، گفتم شاید اونو میگید( چون با اینکه شبیه هستند اما مرتبه متفاوتی دارن ).
بله. بیشتر منظورم همون دو تا تست بود.
(۱۰ مهر ۱۳۹۰ ۱۱:۲۲ ب.ظ)yaali نوشته شده توسط: بله. بیشتر منظورم همون دو تا تست بود.عکسش رو بزار تا بگم چی به چیه
سوالات رو پیوست کردم.
دوتا مال کتاب آقای مقسمی و دوتا مال کتاب آقای یوسفی که با نام عکس‌ها مشخص کرده ام.
اما جواب این بزرگواران:
آقای یوسفی:
سوال اول: n
سوال دوم: n^2
آقای مقسمی:
سوال اول:n
سوال دوم: n^2
(۱۰ مهر ۱۳۹۰ ۱۱:۴۴ ب.ظ)yaali نوشته شده توسط: سوالات رو پیوست کردم.
دوتا مال کتاب آقای مقسمی و دوتا مال کتاب آقای یوسفی که با نام عکس‌ها مشخص کرده ام.
اما جواب این بزرگواران:
آقای یوسفی:
سوال اول: n
سوال دوم: n^2
آقای مقسمی:
سوال اول:n
سوال دوم: n^2
خودم فکر می کنم بحث سر کلمات زمان اجرا و مرتبه اجرا هستش.
ببین در سوال اول یک رابطه داری که توی اون n یک مقدار ثابت هست یعنی توی هزینه‌ها اعمال نمیشه( در واقع برای محاسبه اون زمانی نیاز نیست چون خودش یه مقداره مثل اینکه بگیم فلان متغیر مقدارش اینه )پس شما فقط باید (T(n-1 رو n بار حساب کنی( مثل یه حلقه for )که زمانش میشه n
اما در سوال بعدی دیگه رابطه بازگشتی داریم و اون n دیگه بمعنای یه عدد ثابت نیست بلکه بمعنای اینکه به ازای (T(n-1 باید ۱-n تا کار صورت بگیره یعنی میشه جمع اعداد۱ تا ۱-n که مرتبه اون n^2 هست . بعارت دیگه:
n-1 <=== n-1 کار
۲-n-2 <=== n کار
.
.
.
۱====> 1 کار
مجموع کارها توانی از ۲ هست.
حالا یه بار دیگه تست‌ها رو بررسی کن.
لطفا در مورد تابع بازگشتی فاکتوریل هم توضیح بفرمایید.
(۱۱ مهر ۱۳۹۰ ۱۲:۰۵ ق.ظ)yaali نوشته شده توسط: لطفا در مورد تابع بازگشتی فاکتوریل هم توضیح بفرمایید:
اینو من فهمیدم: اگه زمان اجرا رو بخواهیم می شه n، چون n بار فراخوانی می شه اما اگه با روش جایگزینی مرتبه‌ی آن را حساب کنیم می شه n فاکتوریل.
اما از کجا بدونیم منظور طراح کدوم یکی هستش؟
ببین اینم مثل بالایه:
الگوریتم: [tex]f(n) = n * f (n-1) [/tex]
پس اگه بخواهی مرتبه اونو حساب کنی، چون خط فوق یک کد هست و نه یک رابطه بازگشتی مقدار خود n، یعنی یه مقدار ثابت، پس مثل اینه که یک for داری با زمان n
اما برای مقدارش شما خود n های بالا رو حساب میکنی( که حساب کردن n در زمان ثابت صورت میگیره یعنی مرتبه اون ۱ هست )یعنی همون مقدار فاکتوریل.
ممنون از پاسخ بسیار خوب آقای مسعود .من خودم قبلا این سوال رو درک نمی کردم و با پاسخ خوبتون باعث میشه هر شبهه ای برطرف بشه . به هر ترتیب ممنون
(۱۱ مهر ۱۳۹۰ ۰۳:۵۰ ب.ظ)لهمشد نوشته شده توسط: ممنون از پاسخ بسیار خوب آقای مسعود .من خودم قبلا این سوال رو درک نمی کردم و با پاسخ خوبتون باعث میشه هر شبهه ای برطرف بشه . به هر ترتیب ممنونخواهش میکنم . خوشحال میشم اگه بتونم به کسی کمک کنم.
سلام
واقعا مرسی که جواب دادین با حوصله
ولی من هنوز نفهمیدم و اصلا سوال خودمم بوده
اگه می تونید یا یه مثال دیگه توضیح بدبد فرق مرتبه و زمان اجرا
ممنون
