۰
subtitle
ارسال: #۱
ارتفاع هیپ درجه d با n گره از چه مرتبه ای است؟
با سلام. عزیزان ارتفاع یک هیپ درجه d و یا هر درخت کاملی با این درجه و تعداد گره های n از چه مرتبه ای میشه؟
۰
ارسال: #۲
RE: ارتفاع هیپ درجه d با n گره؟
تله گذاشتی؟!
ارتفاعش که میشه: [tex]\left \lceil \log_{d}(d-1) \log_{d}n -1 \right \rceil[/tex]
{فکر نکنی اینو بلد بودم!
از توی اینترنت پیداش کردم.}
ولی شما مرتبه‌ی پیدا کردن ارتفاع رو خواستی،که از دید من میشه [tex]O(1)[/tex] چونکه n را توی صورت سوال داریم.ولی اگر n را نداشتیم مرتبه میشد[tex]O(\log_{d}n)[/tex] (اگر d رو کمتر از n در نظر بگیریم.)
ارتفاعش که میشه: [tex]\left \lceil \log_{d}(d-1) \log_{d}n -1 \right \rceil[/tex]
{فکر نکنی اینو بلد بودم!
از توی اینترنت پیداش کردم.}ولی شما مرتبه‌ی پیدا کردن ارتفاع رو خواستی،که از دید من میشه [tex]O(1)[/tex] چونکه n را توی صورت سوال داریم.ولی اگر n را نداشتیم مرتبه میشد[tex]O(\log_{d}n)[/tex] (اگر d رو کمتر از n در نظر بگیریم.)
۰
ارسال: #۳
RE: ارتفاع هیپ درجه d با n گره؟
اگه ارتفاع رو بخوایم بدونیم ،واسه یه درخت کامل درجه d با n گره ارتفاع رو همیشه نمیشه گرفت [tex]( log_{d}(n))[/tex].آخه من واسه d=3 حساب کردم .اگه ۴ تا عنصر داشته باشیم ارتفاع با فرمول بالا میشه۲ در حالیکه باید ۱ بدست بیاد.
۰
ارسال: #۴
RE: ارتفاع هیپ درجه d با n گره؟
باید دقت کنید که در آخرین سطح یک درخت کامل تعداد گره‌ها میتونه بین ۱ تا [tex]d^{h}[/tex]
باشه .
پس نمیتونید فرمول خاصی برای اون بگید.مگر اینکه تعداد n رو داشته باشید سعی کنید فرمول حفظ نکنید با تحلیل درخت ارتفاع رو محاسبه کنید.
باشه .
پس نمیتونید فرمول خاصی برای اون بگید.مگر اینکه تعداد n رو داشته باشید سعی کنید فرمول حفظ نکنید با تحلیل درخت ارتفاع رو محاسبه کنید.
۰
ارسال: #۵
RE: ارتفاع هیپ درجه d با n گره؟
بله من یه لحظه با درخت پر اشتباه کردم بعدش که گفتم باید خودتون تحلیل کنید و فرمول قبل حداکثر n رو به ما میداد . حداقلش هم میشه
[tex]d^{h}-1/d-1 1 =d^{h} d-2/d-1[/tex]
برای اون مثال که d=3 و n=4 بود چون درخت پره. از فرمول اول میریم یعنی
[tex]d^{h 1}-1/d-1 [/tex]
[tex]4=3^{h 1}-1/3-1 [/tex] یعنی h+1 میشه ۲ و h=1 بدست میاد.
البته گفتم این دو فرمول برای وقتی هست که یا حداقل گره رو داشته باشیم یا حداکثر و در هر صورت ارتفاع h هست.
[tex]d^{h}-1/d-1 1 =d^{h} d-2/d-1[/tex]
برای اون مثال که d=3 و n=4 بود چون درخت پره. از فرمول اول میریم یعنی
[tex]d^{h 1}-1/d-1 [/tex]
[tex]4=3^{h 1}-1/3-1 [/tex] یعنی h+1 میشه ۲ و h=1 بدست میاد.
البته گفتم این دو فرمول برای وقتی هست که یا حداقل گره رو داشته باشیم یا حداکثر و در هر صورت ارتفاع h هست.
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
 |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۴,۸۶۴ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
| مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۳۶۹ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
| مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۳۰ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
| حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۲,۹۴۴ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
| محاسبه ارتفاع درخت.... | baharkhanoom | ۳ | ۸,۰۸۴ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ آخرین ارسال: mohsentafresh |
|
| مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۴۹۲ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
| مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۷۹۸ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
| مرتبه مانی | Sanazzz | ۳ | ۳,۷۰۰ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
| سطح و عمق و ارتفاع درخت | remove | ۵ | ۱۱,۳۷۹ |
۱۹ اسفند ۱۳۹۷ ۰۴:۲۴ ب.ظ آخرین ارسال: mstfvi |
|
 |
رسم درخت با ۲۶ گره و ارتفاع کمینه | porseshgar | ۰ | ۱,۷۳۶ |
۱۶ بهمن ۱۳۹۷ ۱۲:۱۱ ب.ظ آخرین ارسال: porseshgar |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close