صفحه‌ها: ۱ ۲
سلام
بچه توی کتاب مقسمی بین مرتبه زمانی دو رابطه‌ی زیر فرق گذاشته.چرا؟؟؟؟؟؟
T(n)=T(n-1)+T(n-1)
T(n)=2T(n-1)
چون مقسمی فرق رابطه بازگشتی و تابع بازگشتی رو نفهمیده. هر دو تاش نمایی هست خیالتون راحت!
اگه این دو تابعی که نوشتید روابط بازگشتی ای باشند که میخوایم زمانشون رو حساب کنیم، رابطه‌ی بازگشتیِ زمان این روابط بازگشتی این طوری هست:
[tex]T(n)=T(n-1) T(n-1) \Rightarrow Time(n)=2Time(n-1)[/tex]
چرا؟ چون که [tex]T(n)[/tex] دو بار تابع [tex]T(n - 1)[/tex] رو فراخوانی میکنه!
[tex]T(n)=2T(n-1) \Rightarrow Time(n)=Time(n-1)[/tex]
اما این جا، تابع [tex]T(n)[/tex] فقط یکبار [tex]T(n - 1)[/tex] رو فراخوانی میکنه و جوابش رو در ۲ ضرب میکنه!
نتیجه‌ی هر دو تابع یکی هست، اما تعداد فراخوانی هاشون و در نتیجه زمانشون متفاوت هست! در واقع اولی کار اضافی انجام میده!
البته من کتاب مقسمی رو ندارم! با فرض این که اینا تابع بازگشتی هستند (تنها فرض درستی که میشد با وجود سوال مطرح شده کرد) جواب دادم!
نه توی کتاب مقسمی اینها تابع نیستند رابطه هستند و مقسمی یه لحظه اشتباه کرده دیگه!
صفحه اش رو ذکر کنید بررسی کنیم. بعید می دونم دیگه این آقای مقسمی اینقدرا هم ....: دی
فکر می کنم واسه شما سوء تفاهم شده. توضیحات دوستان که درست بود، اما فکر کنم شما زیاد خوندین، قاطی شده با هم
صفحه ۶۱ !
من مطمئنم که اشتباه کردن ........: دی
آفاق جون بنده از طرفداران!!! پر و پا قرص سوتی های ایشون هستم البته
صفحه ای که من ازش سوال پرسیدم جدول صفحه‌ی ۲۶ بود.
می دونید چرا به شک افتادم؟
فرض کنید سر کنکور دو جور برنامه به ما می دهند می گند مرتبه‌ی زمانی شو بدست آورید.
اولی:
int T(int n
{
if(n>=1
return 1
else
return T(n-1)+T(n-1)
{
دومی:
int T(int n
{
if(n>=1
return 1
else
x++
return T(n-1)+T(n-1)
{
مقسمی تو مورد اول گفته عمل اصلی تعداد فراخوانی های تابع است و باید اونا رو حساب کنیم.
ولی تو مورد دوم فکر کنم ما همیشه x++ را عمل اصلی می گرفتیم.
این دوتا تو مرتبه زمانی فرقی با هم ندارند؟؟
حالا اینجا رو ببینید:
این عکس از صفحه ۱۳ طراحی الگوریتم راهیان ارشده
گفته وقتی داشته باشیم t(n)= 2t(n-1) میشه O(n)=n
ولی وقتی T(n)= T(n-1)+T(n-1) میشه O(n)= 2^n
چیزی که گفته درسته؟
[attachment=373]
(۱۳ بهمن ۱۳۸۹ ۰۱:۳۰ ب.ظ)zr2358 نوشته شده توسط: حالا اینجا رو ببینید:
این عکس از صفحه ۱۳ طراحی الگوریتم راهیان ارشده
گفته وقتی داشته باشیم t(n)= 2t(n-1) میشه O(n)=n
ولی وقتی T(n)= T(n-1)+T(n-1) میشه O(n)= 2^n
چیزی که گفته درسته؟
بله درسته. شما باید به این توجه کنید که یک تابع برای اجراش چه توابعی رو فراخوانی می کنه. بعد رابطه ای بین مدت زمان اجرای تابع اصلی با توابع فراخوانی شده پیدا کنید. معیار اصلی اینه که وقتی دوبار تابع f(n-1 فراخوانی بشه، باید مدت زمان اش در ۲ ضرب بشه، چون تمام این پروسه دوبار واقعا اجرا می شه و نه یک بار
(۱۳ بهمن ۱۳۸۹ ۰۱:۱۱ ق.ظ)Maryam-X نوشته شده توسط: صفحه ای که من ازش سوال پرسیدم جدول صفحه‌ی ۲۶ بود.
می دونید چرا به شک افتادم؟
فرض کنید سر کنکور دو جور برنامه به ما می دهند می گند مرتبه‌ی زمانی شو بدست آورید.
اولی:
int T(int n
{
if(n>=1
return 1
else
return T(n-1)+T(n-1)
{
دومی:
int T(int n
{
if(n>=1
return 1
else
x++
return T(n-1)+T(n-1)
{
مقسمی تو مورد اول گفته عمل اصلی تعداد فراخوانی های تابع است و باید اونا رو حساب کنیم.
ولی تو مورد دوم فکر کنم ما همیشه x++ را عمل اصلی می گرفتیم.
این دوتا تو مرتبه زمانی فرقی با هم ندارند؟؟
اینها رو با هم قاطی نکنید. این که عمل اصلی چیه یه صحبته و بحث روابط بازگشتی یه بحث دیگه است.
در روابط بازگشتی که همونی که در مثال اول گفتید هست. با همون شیوه مدت زمان اجرا رو احساب کنید و تمام
در مورد مثال دوم تون
اگر سوال بشه که عمل x++ چند بار اجرا می شه حرف شما درسته، در غیر اینصورت مدت زمانی که اجرای برنامه طول می کشه، به x++ ربطی نداره بلکه بازم باید همون مرتبه اجرایی بازگشتی رو حساب کنید
خیلی ممنون از توضیحات bijibuji
این درست که اگه دو بار فراخوانی نوشته بشه زمان اجراشم ۲ برابر میشه
خب اگه این یه رابطه بود چی؟ فرقی می کرد؟
توی کتاب رابطه‌ها رو هم با همین روش رفته
فکر کنم به قول آفاق که میگه مقسمی فرق اینا رو نفهمیده منم باید اضافه کنین
فکر کنم منم نفهمیدم درست
اگر در فراخوانی فقط یک بار نوشته شده بود T(n-1 خوب فقط یک بار لحاظ می شه. سوالتون رو دقیق بپرسید تا زودتر متوجه بشید.
درسته
من میگم که مگه زمان اجرای رابطه بازگشتی با تابع چه تفاوتی با هم دارند؟
مگه در هر دو اگه یک بار نوشته بشه زمانش کمتر از وقتی نیست که دو بار نوشته بشه؟
منظورم اینه که مرتبه زمانی هر کدام از این دو در تابع و رابطه بازگشتی چی میشه؟
T(n)=T(n-1)+T(n-1)
T(n)=2T(n-1)
حسابی تفاوتشون فکرمو مشغول کرده
ممنون میشم توضیح بدین
(۱۳ بهمن ۱۳۸۹ ۰۱:۳۰ ب.ظ)zr2358 نوشته شده توسط: حالا اینجا رو ببینید:
این عکس از صفحه ۱۳ طراحی الگوریتم راهیان ارشده
گفته وقتی داشته باشیم t(n)= 2t(n-1) میشه O(n)=n
ولی وقتی T(n)= T(n-1)+T(n-1) میشه O(n)= 2^n
چیزی که گفته درسته؟
اتفاقا کتاب مقسمی هم همین رو گفته!
قضیه بسیار شفاف‌تر از اونه که فکرش رو می کنید. برای یک لحظه مقسمی و پوران و فلان و فلان رو بذارید کنار
یک تابع دارید. در متن اش نوشته شده x=x+1
این تابع یک بار اجرا می شه و نتیجه رو بر می گردونه و تمام
حالا اکر تابع خودش رو یک بار صدا زد زمان اجرای تابع اولیه می شه زمان تابع صدا زده شده به علاوه ۱
حالا اگر دوبار خودش رو صدا زد، زمان اش می شه ۲ برابر زمان تابع صدا زده شده به علاوه ۱
-------------
این قصه رو که ازش بگذریم می رسیم به اینکه چطوری بفهمیم که تابع صدا زده شده چقدر هست زمان اش؟
این با استفاده از رابطه بازگشتی حل می شهو همون مستر و اینها
--------------
حالا یه داستان( یه تیریک تست )اضافه شده و اون اینکه یک تابع بازگشتی رو می دن و می گن این زمان اجرای تابع دیگری است. خوب حل اش می کنیم و مشکلی هم نداره
اما نکته اینجاست که بعضی طراح های شیطون میان و می گن این رابطه خود تابع بازگشتی هست. حالا شما زمان اش رو حساب کنید.
در حالت اول شما مقدار (فرمول) خود تابع رو حساب کردید
در حالت دوم مرتبه اجرایی اش رو
همین