اینا به چه روشی حل میشن؟
۱) [tex]T(n)=T(n-1)\: \frac{1}{n}[/tex]
۲) [tex]T(n)=T(n-1)\: \: \log n[/tex]
۳) [tex]T(n)=T(n-2)\: \: 2\log n[/tex]
۴) [tex]T(n)=T(n-1)\: \: T(\frac{n}{2}) n[/tex]
[tex]T(n)=T(n-1) \frac{1}{n}[/tex]
[tex]T(n)=T(n-2) \frac{1}{n-1} \frac{1}{n}[/tex]
[tex]T(n)=T(n-3) \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n}[/tex]
...
[tex]T(n)=1 .... \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n}=\ln(n)=\log n[/tex]
////////////////////////////////////////////////////////
[tex]T(n)=T(n-1) \log n[/tex]
[tex]T(n)=T(n-2) \log(n-1) \log n[/tex]
[tex]T(n)=T(n-3) \log(n-2) \log(n-1) \log n[/tex]
...
[tex]T(n)=\log(1) \log(2) ... \log(n-2) \log(n-1) \log n\: =\: \log(1\times2\times3\times...\times n)=\log n!=\theta(nlogn)[/tex]
///////////////////////////////////////////////////////////
[tex]T(n)=T(n-1) T(\frac{n}{2}) n[/tex]
برای حل این اگه بخوایم با بازگشتی حلش کنیم اینطوری میشه:
[tex]T(n)=T(n-2) T(\frac{(n-1)}{2}) T(\frac{n}{2}) (n-1) n[/tex]
[tex]T(n)=T(n-3) T(\frac{(n-2)}{2}) T(\frac{(n-1)}{2}) T(\frac{n}{2}) (n-2) (n-1) n[/tex]
....
ببین رابطه از دو قسمت تشکیل شده که کاملا مجزا هستن برای همین به صورت تقریبی پیچیدگیش رو در نظر میگیریم. اگه دقت کنی قسمت دوم از پیچیدگی [tex]n^2[/tex] هستن .توی این سوالا اون قسمتی از معادله که رشد سریعتر هست رو خذف میکنیم. الان اینجا [tex]T(\frac{n}{2})[/tex] رو که حذف کنیم معادله اینطوری میشه [tex]T(n)=T(n-1) n[/tex] که اینم از مرتبه دو هست.
من باشم همه رو با جایگزینی حل میکنم
مرسی
من تو روش جایگزینی گیر میکنم.
در رابطه ی آخر چرا [tex]T(\frac{n}{2})[/tex] رو حذف کردید؟
ببینید درست میگم؟
یه قسمت میشه [tex]n^2[/tex]
یه قسمت دیگه میشه [tex]\frac{1}{2}n^2[/tex]
درسته؟
بعد چون دومی ضریب داره رشدش سریعتره آره؟
(۱۷ دى ۱۳۹۳ ۰۹:۰۵ ق.ظ)Ametrine نوشته شده توسط: مرسی
من تو روش جایگزینی گیر میکنم.
در رابطه ی آخر چرا [tex]T(\frac{n}{2})[/tex] رو حذف کردید؟
ببینید درست میگم؟
یه قسمت میشه [tex]n^2[/tex]
یه قسمت دیگه میشه [tex]\frac{1}{2}n^2[/tex]
درسته؟
بعد چون دومی ضریب داره رشدش سریعتره آره؟
به این دلیل که رابطه بازگشتی از دو قسمت تشکیل شده یکی [tex]T(n-1)[/tex] و اون یکی هم [tex]T(\frac{n}{2})[/tex] بین این دوتا هم جمع هست. پس وقتی بخوایم پیچیدگی رابطه رو حساب کنیم اونی که زمان بیشتری میبره مشخص کنه پیچیدگی رابطه هست. الان بین این دو تا [tex]T(\frac{n}{2})[/tex] سرعت بیشتری داره پس میزاریمش کنار و مثل اینه که رابطه اینطوری باشه [tex]T(n)=T(n-1) n[/tex].
دقیقا توی درخت بازگشتی از همین روش برای مشخص کردن ارتفاع درخت استفاده میشه. اونجام به همین دلیل هستش.
موفق باشید
(۱۷ دى ۱۳۹۳ ۰۹:۲۸ ق.ظ)shayesteb نوشته شده توسط: به این دلیل که رابطه بازگشتی از دو قسمت تشکیل شده یکی [tex]T(n-1)[/tex] و اون یکی هم [tex]T(\frac{n}{2})[/tex] بین این دوتا هم جمع هست. پس وقتی بخوایم پیچیدگی رابطه رو حساب کنیم اونی که زمان بیشتری میبره مشخص کنه پیچیدگی رابطه هست. الان بین این دو تا [tex]T(\frac{n}{2})[/tex] سرعت بیشتری داره پس میزاریمش کنار و مثل اینه که رابطه اینطوری باشه [tex]T(n)=T(n-1) n[/tex].من جوابم رو نگرفتم.
دقیقا توی درخت بازگشتی از همین روش برای مشخص کردن ارتفاع درخت استفاده میشه. اونجام به همین دلیل هستش.
موفق باشید
فهمیدم که دو قسمته،
اونی که سرعتش بیشتره حذف میشه؟ یعنی چی که سرعتش بیشتره؟ یعنی زودتر به صفر میرسه؟
از کجا میفهمیم [tex]T(\frac{n}{2})[/tex] سرعتش بیشتره؟
چرا سرعتش بیشتره؟؟؟؟
(سرعت بیشتر و رشد بیشتر با هم معادلن؟!)
(۱۷ دى ۱۳۹۳ ۱۰:۲۹ ق.ظ)Ametrine نوشته شده توسط: من جوابم رو نگرفتم.
فهمیدم که دو قسمته،
اونی که سرعتش بیشتره حذف میشه؟ یعنی چی که سرعتش بیشتره؟ یعنی زودتر به صفر میرسه؟
از کجا میفهمیم [tex]T(\frac{n}{2})[/tex] سرعتش بیشتره؟
چرا سرعتش بیشتره؟؟؟؟
(سرعت بیشتر و رشد بیشتر با هم معادلن؟!)
جوابش روشن هست. به این دلیل سرعت [tex]T(\frac{n}{2})[/tex] بیشتر هست چون هر بار ان تقسیم بر دو میشه ولی [tex]T(n-1)[/tex] هر بار یکی ازش کم میشه. مشخصه تابعی که هر بار تقسیم بر دو میشه سرعت بیشتری داره و زودتر به یک میرسه.(تابعی که سرعت بیشتری داره رشد کمتری داره
)
(۱۷ دى ۱۳۹۳ ۱۱:۲۱ ق.ظ)shayesteb نوشته شده توسط:ممنون، الان روشن شد(17 دى ۱۳۹۳ ۱۰:۲۹ ق.ظ)Ametrine نوشته شده توسط: من جوابم رو نگرفتم.
فهمیدم که دو قسمته،
اونی که سرعتش بیشتره حذف میشه؟ یعنی چی که سرعتش بیشتره؟ یعنی زودتر به صفر میرسه؟
از کجا میفهمیم [tex]T(\frac{n}{2})[/tex] سرعتش بیشتره؟
چرا سرعتش بیشتره؟؟؟؟
(سرعت بیشتر و رشد بیشتر با هم معادلن؟!)
جوابش روشن هست. به این دلیل سرعت [tex]T(\frac{n}{2})[/tex] بیشتر هست چون هر بار ان تقسیم بر دو میشه ولی [tex]T(n-1)[/tex] هر بار یکی ازش کم میشه. مشخصه تابعی که هر بار تقسیم بر دو میشه سرعت بیشتری داره و زودتر به یک میرسه.(تابعی که سرعت بیشتری داره رشد کمتری داره
تو جزوه کلاس دکتر یوسفی هم پیداش کردم.
(۱۶ دى ۱۳۹۳ ۰۹:۴۲ ب.ظ)miladcr7 نوشته شده توسط: من باشم همه رو با جایگزینی حل میکنم
خب اوناهم با جایگزینی حل کردن دیگه.
منظورتون اینه که عدد میگذاری؟
(۱۷ دى ۱۳۹۳ ۱۲:۲۰ ب.ظ)ana9940 نوشته شده توسط:(16 دى ۱۳۹۳ ۰۹:۴۲ ب.ظ)miladcr7 نوشته شده توسط: من باشم همه رو با جایگزینی حل میکنم
خب اوناهم با جایگزینی حل کردن دیگه.
منظورتون اینه که عدد میگذاری؟
سلام.تاریخ پست رو ببینید این اولین جواب بوده!!!!
همون روشی که بچه ها رفتن
(۱۷ دى ۱۳۹۳ ۱۲:۲۲ ب.ظ)miladcr7 نوشته شده توسط: سلام.تاریخ پست رو ببینید این اولین جواب بوده!!!!
همون روشی که بچه ها رفتن
اتفاقا تاریخ پست رو دیدم ، ارسال شما یه دقیقه بعد از ارسال جواب shayesteb بوده!
(۱۶ دى ۱۳۹۳ ۰۹:۴۱ ب.ظ)shayesteb نوشته شده توسط: [tex]T(n)=T(n-1) \frac{1}{n}[/tex]
[tex]T(n)=T(n-2) \frac{1}{n-1} \frac{1}{n}[/tex]
[tex]T(n)=T(n-3) \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n}[/tex]
...
[tex]T(n)=1 .... \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n}=\ln(n)=\log n[/tex]
////////////////////////////////////////////////////////
[tex]T(n)=T(n-1) \log n[/tex]
[tex]T(n)=T(n-2) \log(n-1) \log n[/tex]
[tex]T(n)=T(n-3) \log(n-2) \log(n-1) \log n[/tex]
...
[tex]T(n)=\log(1) \log(2) ... \log(n-2) \log(n-1) \log n\: =\: \log(1\times2\times3\times...\times n)=\log n!=\theta(nlogn)[/tex]
///////////////////////////////////////////////////////////
[tex]T(n)=T(n-1) T(\frac{n}{2}) n[/tex]
برای حل این اگه بخوایم با بازگشتی حلش کنیم اینطوری میشه:
[tex]T(n)=T(n-2) T(\frac{(n-1)}{2}) T(\frac{n}{2}) (n-1) n[/tex]
[tex]T(n)=T(n-3) T(\frac{(n-2)}{2}) T(\frac{(n-1)}{2}) T(\frac{n}{2}) (n-2) (n-1) n[/tex]
....
ببین رابطه از دو قسمت تشکیل شده که کاملا مجزا هستن برای همین به صورت تقریبی پیچیدگیش رو در نظر میگیریم. اگه دقت کنی قسمت دوم از پیچیدگی [tex]n^2[/tex] هستن .توی این سوالا اون قسمتی از معادله که رشد سریعتر هست رو خذف میکنیم. الان اینجا [tex]T(\frac{n}{2})[/tex] رو که حذف کنیم معادله اینطوری میشه [tex]T(n)=T(n-1) n[/tex] که اینم از مرتبه دو هست.
(۱۶ دى ۱۳۹۳ ۰۹:۴۱ ب.ظ)shayesteb نوشته شده توسط: [tex]T(n)=T(n-1) \frac{1}{n}[/tex]
[tex]T(n)=T(n-2) \frac{1}{n-1} \frac{1}{n}[/tex]
[tex]T(n)=T(n-3) \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n}[/tex]
...
[tex]T(n)=1 .... \frac{1}{n-2} \frac{1}{n-1} \frac{1}{n}=\ln(n)=\log n[/tex]
////////////////////////////////////////////////////////
[tex]T(n)=T(n-1) \log n[/tex]
[tex]T(n)=T(n-2) \log(n-1) \log n[/tex]
[tex]T(n)=T(n-3) \log(n-2) \log(n-1) \log n[/tex]
...
[tex]T(n)=\log(1) \log(2) ... \log(n-2) \log(n-1) \log n\: =\: \log(1\times2\times3\times...\times n)=\log n!=\theta(nlogn)[/tex]
///////////////////////////////////////////////////////////
[tex]T(n)=T(n-1) T(\frac{n}{2}) n[/tex]
برای حل این اگه بخوایم با بازگشتی حلش کنیم اینطوری میشه:
[tex]T(n)=T(n-2) T(\frac{(n-1)}{2}) T(\frac{n}{2}) (n-1) n[/tex]
[tex]T(n)=T(n-3) T(\frac{(n-2)}{2}) T(\frac{(n-1)}{2}) T(\frac{n}{2}) (n-2) (n-1) n[/tex]
....
ببین رابطه از دو قسمت تشکیل شده که کاملا مجزا هستن برای همین به صورت تقریبی پیچیدگیش رو در نظر میگیریم. اگه دقت کنی قسمت دوم از پیچیدگی [tex]n^2[/tex] هستن .توی این سوالا اون قسمتی از معادله که رشد سریعتر هست رو خذف میکنیم. الان اینجا [tex]T(\frac{n}{2})[/tex] رو که حذف کنیم معادله اینطوری میشه [tex]T(n)=T(n-1) n[/tex] که اینم از مرتبه دو هست.
T(n)=T(n−۱)+logn
T(n)=T(n−۲)+log(n−۱)+logn
T(n)=T(n−۳)+log(n−۲)+log(n−۱)+logn
...
T(n)=log(1)+log(2)+...+log(n−۲)+log(n−۱)+logn=log(1×۲×۳×...×n)=logn!=θ(nlogn)
این قسمت مبهمه چرا ضربشون کردین؟
(۱۷ دى ۱۳۹۳ ۱۲:۳۸ ب.ظ)dokhtare payiz نوشته شده توسط: T(n)=log(1)+log(2)+...+log(n−۲)+log(n−۱)+logn=log(1×۲×۳×...×n)=logn!=θ(nlogn)
این قسمت مبهمه چرا ضربشون کردین؟
از خواص لگاریتم بود دیگه:
[tex]\log a \log b=\log ab[/tex]
(۱۷ دى ۱۳۹۳ ۱۲:۲۴ ب.ظ)ana9940 نوشته شده توسط: اتفاقا تاریخ پست رو دیدم ، ارسال شما یه دقیقه بعد از ارسال جواب shayesteb بوده!shayesteb جوابشون رو ویرایش کردن.
دمه کنکوری دعوا نکنید خواهشاً