زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۴:۰۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

رابطه بازگشتی؛ حل از کدام روش؟

ارسال:
  

Ametrine پرسیده:

Question رابطه بازگشتی؛ حل از کدام روش؟

اینا به چه روشی حل میشن؟

۱) [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]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

shayesteb پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

[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] که اینم از مرتبه دو هست.
نقل قول این ارسال در یک پاسخ

ارسال:
  

Ametrine پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

مرسی
من تو روش جایگزینی گیر میکنم.
در رابطه ی آخر چرا [tex]T(\frac{n}{2})[/tex] رو حذف کردید؟

ببینید درست میگم؟
یه قسمت میشه [tex]n^2[/tex]
یه قسمت دیگه میشه [tex]\frac{1}{2}n^2[/tex]
درسته؟
بعد چون دومی ضریب داره رشدش سریعتره آره؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

shayesteb پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۰۹:۰۵ ق.ظ)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].

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

موفق باشید Smile
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Ametrine پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۰۹:۲۸ ق.ظ)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].

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

موفق باشید Smile
من جوابم رو نگرفتم.
فهمیدم که دو قسمته،
اونی که سرعتش بیشتره حذف میشه؟ یعنی چی که سرعتش بیشتره؟ یعنی زودتر به صفر میرسه؟
از کجا میفهمیم [tex]T(\frac{n}{2})[/tex] سرعتش بیشتره؟
چرا سرعتش بیشتره؟؟؟؟
(سرعت بیشتر و رشد بیشتر با هم معادلن؟!)
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

shayesteb پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۱۰:۲۹ ق.ظ)Ametrine نوشته شده توسط:  من جوابم رو نگرفتم.
فهمیدم که دو قسمته،
اونی که سرعتش بیشتره حذف میشه؟ یعنی چی که سرعتش بیشتره؟ یعنی زودتر به صفر میرسه؟
از کجا میفهمیم [tex]T(\frac{n}{2})[/tex] سرعتش بیشتره؟
چرا سرعتش بیشتره؟؟؟؟
(سرعت بیشتر و رشد بیشتر با هم معادلن؟!)

جوابش روشن هست. به این دلیل سرعت [tex]T(\frac{n}{2})[/tex] بیشتر هست چون هر بار ان تقسیم بر دو میشه ولی [tex]T(n-1)[/tex] هر بار یکی ازش کم میشه. مشخصه تابعی که هر بار تقسیم بر دو میشه سرعت بیشتری داره و زودتر به یک میرسه.(تابعی که سرعت بیشتری داره رشد کمتری داره Smile)
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Ametrine پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۱۱:۲۱ ق.ظ)shayesteb نوشته شده توسط:  
(17 دى ۱۳۹۳ ۱۰:۲۹ ق.ظ)Ametrine نوشته شده توسط:  من جوابم رو نگرفتم.
فهمیدم که دو قسمته،
اونی که سرعتش بیشتره حذف میشه؟ یعنی چی که سرعتش بیشتره؟ یعنی زودتر به صفر میرسه؟
از کجا میفهمیم [tex]T(\frac{n}{2})[/tex] سرعتش بیشتره؟
چرا سرعتش بیشتره؟؟؟؟
(سرعت بیشتر و رشد بیشتر با هم معادلن؟!)

جوابش روشن هست. به این دلیل سرعت [tex]T(\frac{n}{2})[/tex] بیشتر هست چون هر بار ان تقسیم بر دو میشه ولی [tex]T(n-1)[/tex] هر بار یکی ازش کم میشه. مشخصه تابعی که هر بار تقسیم بر دو میشه سرعت بیشتری داره و زودتر به یک میرسه.(تابعی که سرعت بیشتری داره رشد کمتری داره Smile)
ممنون، الان روشن شد Smile
تو جزوه کلاس دکتر یوسفی هم پیداش کردم.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

dokhtare payiz پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۶ دى ۱۳۹۳ ۰۹:۴۱ ب.ظ)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)
این قسمت مبهمه چرا ضربشون کردین؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Ametrine پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۱۲:۳۸ ب.ظ)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 بوده! Cool
shayesteb جوابشون رو ویرایش کردن.
دمه کنکوری دعوا نکنید خواهشاً
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۰
  

MiladCr7 پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

من باشم همه رو با جایگزینی حل میکنمSmileSmile
نقل قول این ارسال در یک پاسخ

ارسال: #۱۱
  

ana9940 پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۶ دى ۱۳۹۳ ۰۹:۴۲ ب.ظ)miladcr7 نوشته شده توسط:  من باشم همه رو با جایگزینی حل میکنمSmileSmile

خب اوناهم با جایگزینی حل کردن دیگه.
منظورتون اینه که عدد میگذاری؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال: #۱۲
  

MiladCr7 پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۱۲:۲۰ ب.ظ)ana9940 نوشته شده توسط:  
(16 دى ۱۳۹۳ ۰۹:۴۲ ب.ظ)miladcr7 نوشته شده توسط:  من باشم همه رو با جایگزینی حل میکنمSmileSmile

خب اوناهم با جایگزینی حل کردن دیگه.
منظورتون اینه که عدد میگذاری؟

سلام.تاریخ پست رو ببینید این اولین جواب بوده!!!!SmileSmileSmile
همون روشی که بچه ها رفتن
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال: #۱۳
  

ana9940 پاسخ داده:

RE: رابطه بازگشتی؛ حل از کدام روش؟

(۱۷ دى ۱۳۹۳ ۱۲:۲۲ ب.ظ)miladcr7 نوشته شده توسط:  سلام.تاریخ پست رو ببینید این اولین جواب بوده!!!!SmileSmileSmile
همون روشی که بچه ها رفتن

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پارسه، مدرسان شریف،ماهان و.... کدام یک بهتره؟؟؟ alim93 ۶۴ ۶۶,۱۵۸ ۰۷ تیر ۱۴۰۱ ۱۲:۵۶ ق.ظ
آخرین ارسال: عزیز دادخواه
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۴ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  نظر در رابطه با استاد داور علیصا ۰ ۱,۴۳۳ ۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ
آخرین ارسال: علیصا
  آزمون آزمایشی ارشد کدام موسسه را شرکت کنیم Ali1991khe ۲ ۳,۱۴۴ ۱۴ آبان ۱۳۹۹ ۱۲:۰۹ ق.ظ
آخرین ارسال: Ali1991khe
  آزمون آزمایشی ارشد کدام موسسه را شرکت کنیم Ali1991khe ۲ ۲,۹۱۹ ۰۸ آبان ۱۳۹۹ ۱۲:۰۴ ب.ظ
آخرین ارسال: Ali1991khe
  کدام زبان برنامه‌نویسی بهترین انتخاب است؟ elecomco ۲ ۲,۷۲۸ ۱۰ شهریور ۱۳۹۹ ۰۵:۱۶ ب.ظ
آخرین ارسال: kilookiloo
  تعداد روش های نوشتن عدد n ss311 ۲ ۲,۹۵۲ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۱,۹۰۷ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
Big Grin کدام منابع برای هوش مصنوعی برای مهندسی پزشکی؟ sajadg ۳ ۴,۰۱۷ ۱۱ آبان ۱۳۹۸ ۰۴:۳۵ ب.ظ
آخرین ارسال: marvelous
  روش برنامه نویسی پویا برای حل فروشنده دوره گرد Mohammad WR10 ۶ ۱۰,۲۷۱ ۱۶ خرداد ۱۳۹۸ ۰۶:۳۲ ب.ظ
آخرین ارسال: Shadik

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close