صفحه‌ها: ۱ ۲
سلام دوستان
رابطه های بازگشتی زیر مگر یکی نیستن پس چرا مرتبه اجرایشون باهم فرق داره لطفا راهنماییم کنید
پیشاپیش متشکرم[tex]T(n)=T(n-1) T(n-1)\: \: \: \: O(2^n)[/tex]
[tex]T(n)=2T(n-1)\: \: \: \: O(n)[/tex]
این دوتا به نظر من یکی هستن(مگه غیر از اینم میشه؟) ولی اون $O(n)$ به نظر من ممکنه گفته باشه که با داینامیک، میشه توی $O(N)$ حسابش کرد ...
(۰۱ آذر ۱۳۹۳ ۱۱:۰۹ ب.ظ)monji_421 نوشته شده توسط: سلام دوستان
رابطه های بازگشتی زیر مگر یکی نیستن پس چرا مرتبه اجرایشون باهم فرق داره لطفا راهنماییم کنید
[tex]T(n)=T(n-1) T(n-1)\: \: \: \: O(2^n)[/tex]
[tex]T(n)=2T(n-1)\: \: \: \: O(n)[/tex]
حدس من اینه یه جارو اشتباه نوشتین و قبل از این بازگشتها تابعی بوده که میخواسته مفهوم اونو بگه. مثالش اشناس. میشه لطفا از جایی که گفتین عکس بزارید؟
(۰۱ آذر ۱۳۹۳ ۱۱:۴۴ ب.ظ)Ava.arshad94 نوشته شده توسط:(01 آذر ۱۳۹۳ ۱۱:۰۹ ب.ظ)monji_421 نوشته شده توسط: سلام دوستان
رابطه های بازگشتی زیر مگر یکی نیستن پس چرا مرتبه اجرایشون باهم فرق داره لطفا راهنماییم کنید
[tex]T(n)=T(n-1) T(n-1)\: \: \: \: O(2^n)[/tex]
[tex]T(n)=2T(n-1)\: \: \: \: O(n)[/tex]
حدس من اینه یه جارو اشتباه نوشتین و قبل از این بازگشتها تابعی بوده که میخواسته مفهوم اونو بگه. مثالش اشناس. میشه لطفا از جایی که گفتین عکس بزارید؟
این یه جدول داخل کتاب مقسمی ک با ترسیم درخت بازگشتی میگه بدست آورده قبلش هم هیچ توضیحی نداده
اگر بین پرانتزا ضرب باشه و صورتش مثل جایی ک خط قرمز کشیدم باشه مرتبه اجرایش به همون صورت ک روبروش نوشته میشه ولی در مورد جمع دوتا نتیجه داده
![[تصویر: 318366_57906741880851768664.jpg]](https://img.manesht.ir/318366_57906741880851768664.jpg)
طبق این عکسی که گذاشتین سمت چپی ها تابع های بازگشتی هستن نه رابطه ی پیچیدگی زمانی.
که برای اولی میشه : [tex]t(n)=t(n-2) 1 \: \Longrightarrow\: t(n)=2^{\frac{n}{2}} [/tex]
برای دومی هم [tex]t(n)=2t(n-1) 1 \: \Longrightarrow\: t(n)=2^n[/tex]
در مورد اون سوال اول که فرقشون رو نوشتید:
برای اولی هم [tex]t(n)=2t(n-1) 1 \: \Longrightarrow\: t(n)=2^n[/tex]
برای دومی [tex]t(n)=t(n-1) 1 \: \Longrightarrow\ :t(n)\in o(n)[/tex]
ینی سمت چپی ها در شکل همه تابع های بازگشتی هستن. شما باید از روی اینها تابع زمانی رو بدست بیارید.
عجب ببخشید واقن من با اینکه تو عنوان سوال نوشتم رابطه بازگشتی ولی تا حالا فک میکردم پیچیدگی زمانی
این گیج بازی منو ب بزرگیه خودتون ببخشید
من در افق محو شدم
این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب
(۰۲ آذر ۱۳۹۳ ۱۱:۳۹ ق.ظ)ziba.O نوشته شده توسط: این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب
ارسال اولشون منظورشونه
(۰۲ آذر ۱۳۹۳ ۱۱:۴۵ ق.ظ)Ava.arshad94 نوشته شده توسط:(02 آذر ۱۳۹۳ ۱۱:۳۹ ق.ظ)ziba.O نوشته شده توسط: این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب
ارسال اولشون منظورشونه
آهان . به نظرم اون دو تا یکین
(۰۲ آذر ۱۳۹۳ ۱۲:۰۵ ب.ظ)Aurora نوشته شده توسط:(02 آذر ۱۳۹۳ ۱۱:۵۲ ق.ظ)ziba.O نوشته شده توسط:کدوم دوتا؟ دو تای اولی؟(02 آذر ۱۳۹۳ ۱۱:۴۵ ق.ظ)Ava.arshad94 نوشته شده توسط:(02 آذر ۱۳۹۳ ۱۱:۳۹ ق.ظ)ziba.O نوشته شده توسط: این دو تا یکی نیستن، یکی وسطش جمعه یکی ضرب
ارسال اولشون منظورشونه
آهان . به نظرم اون دو تا یکین
آره دوتای اولی که تو اولین پست گذاشتن
نه دوتای اولی با در نظر گرفتن اینکه هر دو رابطه بازگشتی هستن و F هستن یکی نیستن.
(۰۲ آذر ۱۳۹۳ ۱۲:۳۰ ب.ظ)Aurora نوشته شده توسط: نه دوتای اولی با در نظر گرفتن اینکه هر دو رابطه بازگشتی هستن و F هستن یکی نیستن.
حالا این شد سواله من. یکی منو بفهمونه چرا یکی نیستن؟
ببینید من درست میگم بازای n من ۸ گذاشتم تو رابطه اول شد درختش ۱۲۸ گره ک دو ب توان ان ولی در رابطه دوم شد همون ۸ گره
دلیلش اینه با درخت باید تعداد گره هارو بدست آورد
خوب بزار این طوری بگم اون دوتای اولی هر دو تابع بازگشتی هستن و رابطه پیچیدگی زمانی نیستن.
اولی که با هم جمع میشن ینی داریم : [tex]f(n)=f(n-1) f(n-1)[/tex] خوب اینا ینی دوتا [tex]t(n-1)[/tex]
ولی دومی یدونه [tex]t(n-1)[/tex] داریم و ۲ فقط درش ضرب میشه.
اولی دو تا [tex]t(n-1)[/tex] محاسبه میشه دومی فقط یکی [tex]t(n-1)[/tex] محاسبه میشه.
اوکیه؟
(۰۲ آذر ۱۳۹۳ ۱۲:۵۹ ب.ظ)Aurora نوشته شده توسط: خوب بزار این طوری بگم اون دوتای اولی هر دو رابطه بازگشتی هستن و رابطه پیچیدگی زمانی نیستن.بهتره بگیم تابع بازگشتی هستن. ما از روی توابع بازگشت، روابط بازگشت مینویسیم و از روی روابط بازگشت مرتبه رو بدست میاریم
اما بنظرم کتاب اینجا واقعا با ابهام نوشته. انگار همه چیزو مخلوط کرده. اگر میخواست بگه تابع، هدر رو نباید اونطوری مینوشت و بهتر بود F بزاره