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

حداکثر ارتفاع درخت T(N)=T(n/2)+T(3n/4)+n^2

ارسال:
  

iroonidotnet پرسیده:

حداکثر ارتفاع درخت T(N)=T(n/2)+T(3n/4)+n^2

چطوری از روی درخت بازگشتی زیر متوجه میشند که حداکثر ارتفاه logn با پایه ۴/۳ هست؟
T(N)=T(n/2)+T(3n/4)+n^2
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

SnowBlind پاسخ داده:

RE: حداکثر ارتفاع درخت 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]
نقل قول این ارسال در یک پاسخ

ارسال:
  

iroonidotnet پاسخ داده:

RE: حداکثر ارتفاع درخت T(N)=T(n/2)+T(3n/4)+n^2

(۱۱ مهر ۱۳۹۲ ۰۱:۰۲ ب.ظ)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
میشود . دلیل جمع را توضیح دهید

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

ارسال:
  

SnowBlind پاسخ داده:

RE: حداکثر ارتفاع درخت T(N)=T(n/2)+T(3n/4)+n^2

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

ارسال:
  

iroonidotnet پاسخ داده:

RE: حداکثر ارتفاع درخت T(N)=T(n/2)+T(3n/4)+n^2

(۱۱ مهر ۱۳۹۲ ۰۲:۵۲ ب.ظ)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]

ممنون دوست عزیز . از این همه تسلط و شیوایی بیان واقعا لذت بردم خیلی بهم کمک کردین . خدا خیرت بده .
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۸۲۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۶۰۱ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۸۴ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۹۱ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۴۰۴ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۱۱۷ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد درخت فراگیر ss311 ۰ ۲,۳۱۵ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  درخت دسترس پذیری برای شبکه های پتری αɾια ۱ ۲,۴۰۸ ۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ
آخرین ارسال: αɾια
  سطح و عمق و ارتفاع درخت remove ۵ ۱۱,۴۰۸ ۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ
آخرین ارسال: mstfvi
  الگوریتم درخت porseshgar ۰ ۱,۶۹۱ ۱۷ بهمن ۱۳۹۷ ۱۲:۲۴ ب.ظ
آخرین ارسال: porseshgar

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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