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

اگه این دو تابعی که نوشتید روابط بازگشتی ای باشند که میخوایم زمانشون رو حساب کنیم، رابطه‌ی بازگشتیِ زمان این روابط بازگشتی این طوری هست:
$T(n)=T(n-1) T(n-1) \Rightarrow Time(n)=2Time(n-1)$
چرا؟ چون که $T(n)$ دو بار تابع $T(n - 1)$ رو فراخوانی میکنه!

$T(n)=2T(n-1) \Rightarrow Time(n)=Time(n-1)$
اما این جا، تابع $T(n)$ فقط یکبار $T(n - 1)$ رو فراخوانی میکنه و جوابش رو در ۲ ضرب میکنه!

نتیجه‌ی هر دو تابع یکی هست، اما تعداد فراخوانی هاشون و در نتیجه زمانشون متفاوت هست! در واقع اولی کار اضافی انجام میده!

---

البته من کتاب مقسمی رو ندارم! با فرض این که اینا تابع بازگشتی هستند (تنها فرض درستی که میشد با وجود سوال مطرح شده کرد) جواب دادم!

نه توی کتاب مقسمی اینها تابع نیستند رابطه هستند و مقسمی یه لحظه اشتباه کرده دیگه!

صفحه اش رو ذکر کنید بررسی کنیم. بعید می دونم دیگه این آقای مقسمی اینقدرا هم ....: دی
فکر می کنم واسه شما سوء تفاهم شده. توضیحات دوستان که درست بود، اما فکر کنم شما زیاد خوندین‌، قاطی شده با هم

صفحه ۶۱ !
من مطمئنم که اشتباه کردن ........: دی

آفاق جون بنده از طرفداران!!! پر و پا قرص سوتی های ایشون هستم البته

صفحه ای که من ازش سوال پرسیدم جدول صفحه‌ی ۲۶ بود.

می دونید چرا به شک افتادم؟
فرض کنید سر کنکور دو جور برنامه به ما می دهند می گند مرتبه‌ی زمانی شو بدست آورید.

اولی:
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

چیزی که گفته درسته؟

(۱۳ بهمن ۱۳۸۹ ۰۱:۳۰ ب.ظ)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++ ربطی نداره بلکه بازم باید همون مرتبه اجرایی بازگشتی رو حساب کنید

(۱۳ بهمن ۱۳۸۹ ۰۱:۳۰ ب.ظ)zr2358 نوشته شده توسط:  حالا اینجا رو ببینید:
این عکس از صفحه ۱۳ طراحی الگوریتم راهیان ارشده
گفته وقتی داشته باشیم t(n)= 2t(n-1) میشه O(n)=n
ولی وقتی T(n)= T(n-1)+T(n-1) میشه O(n)= 2^n

چیزی که گفته درسته؟

اتفاقا کتاب مقسمی هم همین رو گفته!

خیلی ممنون از توضیحات bijibuji
این درست که اگه دو بار فراخوانی نوشته بشه زمان اجراشم ۲ برابر میشه
خب اگه این یه رابطه بود چی؟ فرقی می کرد؟
توی کتاب رابطه‌ها رو هم با همین روش رفته
فکر کنم به قول آفاق که میگه مقسمی فرق اینا رو نفهمیده منم باید اضافه کنین
فکر کنم منم نفهمیدم درست

اگر در فراخوانی فقط یک بار نوشته شده بود T(n-1 خوب فقط یک بار لحاظ می شه. سوالتون رو دقیق بپرسید تا زودتر متوجه بشید.

درسته
من میگم که مگه زمان اجرای رابطه بازگشتی با تابع چه تفاوتی با هم دارند؟
مگه در هر دو اگه یک بار نوشته بشه زمانش کمتر از وقتی نیست که دو بار نوشته بشه؟
منظورم اینه که مرتبه زمانی هر کدام از این دو در تابع و رابطه بازگشتی چی میشه؟

T(n)=T(n-1)+T(n-1)
T(n)=2T(n-1)

حسابی تفاوتشون فکرمو مشغول کرده
ممنون میشم توضیح بدین

قضیه بسیار شفاف‌تر از اونه که فکرش رو می کنید. برای یک لحظه مقسمی و پوران و فلان و فلان رو بذارید کنار
یک تابع دارید. در متن اش نوشته شده x=x+1
این تابع یک بار اجرا می شه و نتیجه رو بر می گردونه و تمام
حالا اکر تابع خودش رو یک بار صدا زد زمان اجرای تابع اولیه می شه زمان تابع صدا زده شده به علاوه ۱
حالا اگر دوبار خودش رو صدا زد‌، زمان اش می شه ۲ برابر زمان تابع صدا زده شده به علاوه ۱

-------------
این قصه رو که ازش بگذریم می رسیم به اینکه چطوری بفهمیم که تابع صدا زده شده چقدر هست زمان اش؟
این با استفاده از رابطه بازگشتی حل می شهو همون مستر و اینها

--------------
حالا یه داستان( یه تیریک تست )اضافه شده و اون اینکه یک تابع بازگشتی رو می دن و می گن این زمان اجرای تابع دیگری است. خوب حل اش می کنیم و مشکلی هم نداره
اما نکته اینجاست که بعضی طراح های شیطون میان و می گن این رابطه خود تابع بازگشتی هست. حالا شما زمان اش رو حساب کنید.

در حالت اول شما مقدار (فرمول) خود تابع رو حساب کردید
در حالت دوم مرتبه اجرایی اش رو

همین

ممنونم
راستش خیلی متوجه حرفاتون نشدم
این تاپیک خیلی اعتماد به نفسم رو پایین آورد!

سوالی که توی پست اول همین تاپیک پرسیده شد و جواب دادید هر دو یکسانه بچه‌ها گفتند مقسمی با تابع اشتباه گرفته
یعنی اگه تابع بود فرق می کرد مرتبه شون؟

توی این ضمیمه شما خانم zr2358 که نوشته $T(n)=T(n-1) c$
خوب این مرتبش $O(n)$ هست و درسته.

ولی دومی
$T(n)=T(n-1) T(n-1) c=2T(n-1) c$

که از مرتبه $O(2^{n})$ هست.

دلیلش اینه که در اولی ما فقط یک تابع رو داریم فراخوانی میکنیم(به خاطر همین ضریب T(n-1 یک است )پس بیشتر از n تا فراخوانی نداریم. c=2 است چون در هر فراخوانی یک ضرب و یک جمع نیز داریم.
ببینید این ۲ که در خود تابع داره ضرب میشه نباید شما رو گمراه کنه این ۲ صرفا یک عدد است که دارد ضرب میشود و مرتبه را فقط یک واحد افزایش میدهد یعنی اگر این ۲ ،۱۰۰۰ هم بود فرقی نداشت.

اما در حالت دوم داریم هر به ازای هر n دو بار تابع فراخوانی میکنیم و این خیلی بده یعنی ۲*۲*۲*..... بار فراخوانی داریم .(شبیه فیبوناچی) خیلی‌ها رو داریم تکراری حساب میکنیم و به خاطر همین مرتبه بالا رفته. c=2 است چون در هر بار فراخوانی دو جمع داریم.

توی کتاب مقسمی متاسفانه اشتباه کرده !

---

(۱۴ بهمن ۱۳۸۹ ۰۱:۱۱ ب.ظ)zr2358 نوشته شده توسط:  ممنونم
راستش خیلی متوجه حرفاتون نشدم
این تاپیک خیلی اعتماد به نفسم رو پایین آورد!

سوالی که توی پست اول همین تاپیک پرسیده شد و جواب دادید هر دو یکسانه بچه‌ها گفتند مقسمی با تابع اشتباه گرفته
یعنی اگه تابع بود فرق می کرد مرتبه شون؟

اگر تابع بود آن ۲ که داشت در تابع ضرب میشد صرفا یک عدد بود که اگر ۱۰۰۰ هم بود تفاوتی نداشت.
اما وقتی دو زیرروال را داریم جمع میزنیم (مثل فیبوناچی )یعنی برای هر کدام باید مقادیر تکراری زیادی حساب کنیم و همانطور که در بالا توضیح دادم مرتبه خیلی بالا میره.

اگه میخواید فرق تابع و رابطه رو بهتر متوجه بشید بهتره اون شبه کدهایی که ضمیمه کردین رو به ازای n=4 یکبار trace کنید(و تعداد + و * رو بدست بیارید) بعد رابطشون رو به ازای n=4 چک کنید. و متوجع تفاوتشون میشید.

(۱۵ بهمن ۱۳۸۹ ۰۳:۲۷ ب.ظ)afagh1389 نوشته شده توسط:  توی این ضمیمه شما خانم zr2358 که نوشته $T(n)=T(n-1) c$
خوب این مرتبش $O(n)$ هست و درسته.

ولی دومی
$T(n)=T(n-1) T(n-1) c=2T(n-1) c$

که از مرتبه $O(2^{n})$ هست.

دلیلش اینه که در اولی ما فقط یک تابع رو داریم فراخوانی میکنیم(به خاطر همین ضریب T(n-1 یک است )پس بیشتر از n تا فراخوانی نداریم. c=2 است چون در هر فراخوانی یک ضرب و یک جمع نیز داریم.
ببینید این ۲ که در خود تابع داره ضرب میشه نباید شما رو گمراه کنه این ۲ صرفا یک عدد است که دارد ضرب میشود و مرتبه را فقط یک واحد افزایش میدهد یعنی اگر این ۲ ،۱۰۰۰ هم بود فرقی نداشت.

اما در حالت دوم داریم هر به ازای هر n دو بار تابع فراخوانی میکنیم و این خیلی بده یعنی ۲*۲*۲*..... بار فراخوانی داریم .(شبیه فیبوناچی) خیلی‌ها رو داریم تکراری حساب میکنیم و به خاطر همین مرتبه بالا رفته. c=2 است چون در هر بار فراخوانی دو جمع داریم.

توی کتاب مقسمی متاسفانه اشتباه کرده !

---

(۱۴ بهمن ۱۳۸۹ ۰۱:۱۱ ب.ظ)zr2358 نوشته شده توسط:  ممنونم
راستش خیلی متوجه حرفاتون نشدم
این تاپیک خیلی اعتماد به نفسم رو پایین آورد!

سوالی که توی پست اول همین تاپیک پرسیده شد و جواب دادید هر دو یکسانه بچه‌ها گفتند مقسمی با تابع اشتباه گرفته
یعنی اگه تابع بود فرق می کرد مرتبه شون؟

اگر تابع بود آن ۲ که داشت در تابع ضرب میشد صرفا یک عدد بود که اگر ۱۰۰۰ هم بود تفاوتی نداشت.
اما وقتی دو زیرروال را داریم جمع میزنیم (مثل فیبوناچی )یعنی برای هر کدام باید مقادیر تکراری زیادی حساب کنیم و همانطور که در بالا توضیح دادم مرتبه خیلی بالا میره.

اگه میخواید فرق تابع و رابطه رو بهتر متوجه بشید بهتره اون شبه کدهایی که ضمیمه کردین رو به ازای n=4 یکبار trace کنید(و تعداد + و * رو بدست بیارید) بعد رابطشون رو به ازای n=4 چک کنید. و متوجع تفاوتشون میشید.

t(n)=at(n-b)
if a!=1 then t(n)=o(a^n/b)
if a=1 then t(n)=o(n)