(۰۲ آذر ۱۳۹۳ ۱۲:۵۹ ب.ظ)Aurora نوشته شده توسط:  خوب بزار این طوری بگم اون دوتای اولی هر دو رابطه بازگشتی هستن و رابطه پیچیدگی زمانی نیستن.

بهتره بگیم تابع بازگشتی هستن. ما از روی توابع بازگشت، روابط بازگشت مینویسیم و از روی روابط بازگشت مرتبه رو بدست میاریم
اما بنظرم کتاب اینجا واقعا با ابهام نوشته. انگار همه چیزو مخلوط کرده. اگر میخواست بگه تابع، هدر رو نباید اونطوری مینوشت و بهتر بود F بزاره

(۰۲ آذر ۱۳۹۳ ۰۱:۰۷ ب.ظ)Ava.arshad94 نوشته شده توسط:  بهتره بگیم تابع بازگشتی هستن. ما از روی توابع بازگشت، روابط بازگشت مینویسیم و از روی روابط بازگشت مرتبه رو بدست میاریم
اما بنظرم کتاب اینجا واقعا با ابهام نوشته. انگار همه چیزو مخلوط کرده. اگر میخواست بگه تابع، هدر رو نباید اونطوری مینوشت و بهتر بود F بزاره

بله درسته اونا تابع هستند و بعدش رابطه بازگشتی. اگر از اول همون f می نوشت دیگه اشتباه نمیشد.

این دوتا به نظر من یکی هستن(مگه غیر از اینم میشه؟) ولی اون $O(n)$ به نظر من ممکنه گفته باشه که با داینامیک، میشه توی $O(N)$ حسابش کرد ...

(۰۱ آذر ۱۳۹۳ ۱۱:۰۹ ب.ظ)monji_421 نوشته شده توسط:  سلام دوستان
رابطه های بازگشتی زیر مگر یکی نیستن پس چرا مرتبه اجرایشون باهم فرق داره لطفا راهنماییم کنید پیشاپیش متشکرم


$T(n)=T(n-1) T(n-1)\: \: \: \: O(2^n)$
$T(n)=2T(n-1)\: \: \: \: O(n)$

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

(۰۱ آذر ۱۳۹۳ ۱۱:۴۴ ب.ظ)Ava.arshad94 نوشته شده توسط:  

(01 آذر ۱۳۹۳ ۱۱:۰۹ ب.ظ)monji_421 نوشته شده توسط:  سلام دوستان
رابطه های بازگشتی زیر مگر یکی نیستن پس چرا مرتبه اجرایشون باهم فرق داره لطفا راهنماییم کنید پیشاپیش متشکرم


$T(n)=T(n-1) T(n-1)\: \: \: \: O(2^n)$
$T(n)=2T(n-1)\: \: \: \: O(n)$

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

این یه جدول داخل کتاب مقسمی ک با ترسیم درخت بازگشتی میگه بدست آورده قبلش هم هیچ توضیحی نداده
اگر بین پرانتزا ضرب باشه و صورتش مثل جایی ک خط قرمز کشیدم باشه مرتبه اجرایش به همون صورت ک روبروش نوشته میشه ولی در مورد جمع دوتا نتیجه داده

طبق این عکسی که گذاشتین سمت چپی ها تابع های بازگشتی هستن نه رابطه ی پیچیدگی زمانی.
که برای اولی میشه : $t(n)=t(n-2) 1 \: \Longrightarrow\: t(n)=2^{\frac{n}{2}}$
برای دومی هم $t(n)=2t(n-1) 1 \: \Longrightarrow\: t(n)=2^n$

در مورد اون سوال اول که فرقشون رو نوشتید:
برای اولی هم $t(n)=2t(n-1) 1 \: \Longrightarrow\: t(n)=2^n$
برای دومی $t(n)=t(n-1) 1 \: \Longrightarrow\ :t(n)\in o(n)$
ینی سمت چپی ها در شکل همه تابع های بازگشتی هستن. شما باید از روی اینها تابع زمانی رو بدست بیارید.

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

این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب

(۰۲ آذر ۱۳۹۳ ۱۱:۳۹ ق.ظ)ziba.O نوشته شده توسط:  این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب

ارسال اولشون منظورشونه

(۰۲ آذر ۱۳۹۳ ۱۱:۴۵ ق.ظ)Ava.arshad94 نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۱۱:۳۹ ق.ظ)ziba.O نوشته شده توسط:  این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب

ارسال اولشون منظورشونه

آهان . به نظرم اون دو تا یکین

(۰۲ آذر ۱۳۹۳ ۱۲:۰۵ ب.ظ)Aurora نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۱۱:۵۲ ق.ظ)ziba.O نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۱۱:۴۵ ق.ظ)Ava.arshad94 نوشته شده توسط:  

(02 آذر ۱۳۹۳ ۱۱:۳۹ ق.ظ)ziba.O نوشته شده توسط:  این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب

ارسال اولشون منظورشونه

آهان . به نظرم اون دو تا یکین

کدوم دوتا؟ دو تای اولی؟

آره دوتای اولی که تو اولین پست گذاشتن

نه دوتای اولی با در نظر گرفتن اینکه هر دو رابطه بازگشتی هستن و F هستن یکی نیستن.

(۰۲ آذر ۱۳۹۳ ۱۲:۳۰ ب.ظ)Aurora نوشته شده توسط:  نه دوتای اولی با در نظر گرفتن اینکه هر دو رابطه بازگشتی هستن و F هستن یکی نیستن.

حالا این شد سواله من. یکی منو بفهمونه چرا یکی نیستن؟

ببینید من درست میگم بازای n من ۸ گذاشتم تو رابطه اول شد درختش ۱۲۸ گره ک دو ب توان ان ولی در رابطه دوم شد همون ۸ گره
دلیلش اینه با درخت باید تعداد گره هارو بدست آورد

(۰۲ آذر ۱۳۹۳ ۱۲:۵۶ ب.ظ)monji_421 نوشته شده توسط:  ببینید من درست میگم بازای n من ۸ گذاشتم تو رابطه اول شد درختش ۱۲۸ گره ک دو ب توان ان ولی در رابطه دوم شد همون ۸ گره
دلیلش اینه با درخت باید تعداد گره هارو بدست آورد

باید اینطوری بگی که اون که ۲ بار نوشته داره ۲ بار فراخوانی میکنه و حافظه رو هم نابود میکنه. اما اون یکی داره ۱ بار فراخوانی میکنه و در ۲ ضرب میکنه. ۲ بار فراخانی کجا، یبار کجا

آره فهمیدم از اون دید هیچ ابهامی ندلره . راس میگین

باتشکر از جمیع دوستان

ببخشید میشه روش رسم درخت اونی که بینش ضرب هست رو یه راهنمایی بگین.