چطوری از روی درخت بازگشتی زیر متوجه میشند که حداکثر ارتفاه logn با پایه ۴/۳ هست؟
T(N)=T(n/2)+T(3n/4)+n^2
(۱۱ مهر ۱۳۹۲ ۱۲:۰۶ ب.ظ)iroonidotnet نوشته شده توسط: چطوری از روی درخت بازگشتی زیر متوجه میشند که حداکثر ارتفاه logn با پایه ۴/۳ هست؟
T(N)=T(n/2)+T(3n/4)+n^2
درخت وقتی به برگ میرسه که داشته باشیم: [tex]T(1)[/tex] و از طرفی فرم کلی گره ها به صورت [tex]T(\frac{n}{2^{i}})[/tex] و
[tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] هستش و اگه این مقادیر رو مساوی یک قرار بدی داریم:
[tex]\frac{n}{(\frac{4}{3})^i} = 1 \rightarrow n ={(\frac{4}{3})^i \rightarrow i = log_{\frac{4}{3}} n [/tex] واسه حالت دیگه هم به همین ترتیب،
و حالا چرا حداکثر ارتفاع میشه دقت کنید کدام یک از این کسر ها دیر تر به یک میرسند؟ [tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] و [tex]T(\frac{n}{2^{i}})[/tex] مسلما رشد [tex]2^{i}[/tex] از [tex](\frac{4}{3})^{i}[/tex] بشتر هستش و کسر [tex]\frac{n}{2^{i}}[/tex] زود تر به یک میرسه تا [tex]\frac{n}{(\frac{4}{3})^i}[/tex]
(۱۱ مهر ۱۳۹۲ ۰۱:۰۲ ب.ظ)SnowBlind نوشته شده توسط:(11 مهر ۱۳۹۲ ۱۲:۰۶ ب.ظ)iroonidotnet نوشته شده توسط: چطوری از روی درخت بازگشتی زیر متوجه میشند که حداکثر ارتفاه logn با پایه ۴/۳ هست؟
T(N)=T(n/2)+T(3n/4)+n^2
درخت وقتی به برگ میرسه که داشته باشیم: [tex]T(1)[/tex] و از طرفی فرم کلی گره ها به صورت [tex]T(\frac{n}{2^{i}})[/tex] و
[tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] هستش و اگه این مقادیر رو مساوی یک قرار بدی داریم:
[tex]\frac{n}{(\frac{4}{3})^i} = 1 \rightarrow n ={(\frac{4}{3})^i \rightarrow i = log_{\frac{4}{3}} n [/tex] واسه حالت دیگه هم به همین ترتیب،
و حالا چرا حداکثر ارتفاع میشه دقت کنید کدام یک از این کسر ها دیر تر به یک میرسند؟ [tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] و [tex]T(\frac{n}{2^{i}})[/tex] مسلما رشد [tex]2^{i}[/tex] از [tex](\frac{4}{3})^{i}[/tex] بشتر هستش و کسر [tex]\frac{n}{2^{i}}[/tex] زود تر به یک میرسه تا [tex]\frac{n}{(\frac{4}{3})^i}[/tex]
با سلام مجدد . واقعا ً ممنون از این همه حوصله و محبتی که فرمودید . دقیقا متوجه شدم .
فقط اگر محبت بفرمایید در خصوص حداکثر ارتفاع رابطه بازگشتی تست سال ۸۹
T(n,k)=T(n/2,k)+T(n,k/4)+kn
که جواب
logn 2+logk 4
میشود . دلیل جمع را توضیح دهید
باز هم تشکر می کنم خیلی بهم کمک کردین
(۱۱ مهر ۱۳۹۲ ۰۲:۴۰ ب.ظ)iroonidotnet نوشته شده توسط:(11 مهر ۱۳۹۲ ۰۱:۰۲ ب.ظ)SnowBlind نوشته شده توسط:(11 مهر ۱۳۹۲ ۱۲:۰۶ ب.ظ)iroonidotnet نوشته شده توسط: چطوری از روی درخت بازگشتی زیر متوجه میشند که حداکثر ارتفاه logn با پایه ۴/۳ هست؟
T(N)=T(n/2)+T(3n/4)+n^2
درخت وقتی به برگ میرسه که داشته باشیم: [tex]T(1)[/tex] و از طرفی فرم کلی گره ها به صورت [tex]T(\frac{n}{2^{i}})[/tex] و
[tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] هستش و اگه این مقادیر رو مساوی یک قرار بدی داریم:
[tex]\frac{n}{(\frac{4}{3})^i} = 1 \rightarrow n ={(\frac{4}{3})^i \rightarrow i = log_{\frac{4}{3}} n [/tex] واسه حالت دیگه هم به همین ترتیب،
و حالا چرا حداکثر ارتفاع میشه دقت کنید کدام یک از این کسر ها دیر تر به یک میرسند؟ [tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] و [tex]T(\frac{n}{2^{i}})[/tex] مسلما رشد [tex]2^{i}[/tex] از [tex](\frac{4}{3})^{i}[/tex] بشتر هستش و کسر [tex]\frac{n}{2^{i}}[/tex] زود تر به یک میرسه تا [tex]\frac{n}{(\frac{4}{3})^i}[/tex]
با سلام مجدد . واقعا ً ممنون از این همه حوصله و محبتی که فرمودید . دقیقا متوجه شدم .
فقط اگر محبت بفرمایید در خصوص حداکثر ارتفاع رابطه بازگشتی تست سال ۸۹
T(n,k)=T(n/2,k)+T(n,k/4)+kn
که جواب
logn 2+logk 4
میشود . دلیل جمع را توضیح دهید
باز هم تشکر می کنم خیلی بهم کمک کردین
اینجا وقتی که [tex]T(\frac{n}{2},k)[/tex] همین جور میره جلو تا برسه(از سمت چپ) [tex]T(1,k)[/tex] که بعد از [tex]log_{2}(n)[/tex] مرتبه اتفاق میافته، حالا [tex]T(1,k)[/tex] هم از سمت راست دوباره همین جور میره جلو تا برسه به [tex]T(1,1)[/tex] که اینم بعد از [tex]log_{4}(k)[/tex] مرحله اتفاغ می افته که در مجموع ارتفاع درخت میشه : [tex]log_{2}(n) log_{4}(k) [/tex]
(۱۱ مهر ۱۳۹۲ ۰۲:۵۲ ب.ظ)SnowBlind نوشته شده توسط:(11 مهر ۱۳۹۲ ۰۲:۴۰ ب.ظ)iroonidotnet نوشته شده توسط:(11 مهر ۱۳۹۲ ۰۱:۰۲ ب.ظ)SnowBlind نوشته شده توسط:(11 مهر ۱۳۹۲ ۱۲:۰۶ ب.ظ)iroonidotnet نوشته شده توسط: چطوری از روی درخت بازگشتی زیر متوجه میشند که حداکثر ارتفاه logn با پایه ۴/۳ هست؟
T(N)=T(n/2)+T(3n/4)+n^2
درخت وقتی به برگ میرسه که داشته باشیم: [tex]T(1)[/tex] و از طرفی فرم کلی گره ها به صورت [tex]T(\frac{n}{2^{i}})[/tex] و
[tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] هستش و اگه این مقادیر رو مساوی یک قرار بدی داریم:
[tex]\frac{n}{(\frac{4}{3})^i} = 1 \rightarrow n ={(\frac{4}{3})^i \rightarrow i = log_{\frac{4}{3}} n [/tex] واسه حالت دیگه هم به همین ترتیب،
و حالا چرا حداکثر ارتفاع میشه دقت کنید کدام یک از این کسر ها دیر تر به یک میرسند؟ [tex]T(\frac{n}{(\frac{4}{3})^i})[/tex] و [tex]T(\frac{n}{2^{i}})[/tex] مسلما رشد [tex]2^{i}[/tex] از [tex](\frac{4}{3})^{i}[/tex] بشتر هستش و کسر [tex]\frac{n}{2^{i}}[/tex] زود تر به یک میرسه تا [tex]\frac{n}{(\frac{4}{3})^i}[/tex]
با سلام مجدد . واقعا ً ممنون از این همه حوصله و محبتی که فرمودید . دقیقا متوجه شدم .
فقط اگر محبت بفرمایید در خصوص حداکثر ارتفاع رابطه بازگشتی تست سال ۸۹
T(n,k)=T(n/2,k)+T(n,k/4)+kn
که جواب
logn 2+logk 4
میشود . دلیل جمع را توضیح دهید
باز هم تشکر می کنم خیلی بهم کمک کردین
اینجا وقتی که [tex]T(\frac{n}{2},k)[/tex] همین جور میره جلو تا برسه(از سمت چپ) [tex]T(1,k)[/tex] که بعد از [tex]log_{2}(n)[/tex] مرتبه اتفاق میافته، حالا [tex]T(1,k)[/tex] هم از سمت راست دوباره همین جور میره جلو تا برسه به [tex]T(1,1)[/tex] که اینم بعد از [tex]log_{4}(k)[/tex] مرحله اتفاغ می افته که در مجموع ارتفاع درخت میشه : [tex]log_{2}(n) log_{4}(k) [/tex]
ممنون دوست عزیز . از این همه تسلط و شیوایی بیان واقعا لذت بردم خیلی بهم کمک کردین . خدا خیرت بده .