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

kمین کوچکترین عنصر در یک هرم کمینه؟

ارسال:
  

Iranian Wizard پرسیده:

kمین کوچکترین عنصر در یک هرم کمینه؟

سلام.یه سوال داشتم.
kمین کوچکترین عنصر در یک هرم کمینه n عنصری رو بصورت کارا با چه مرتبه ای میشه پیدا کرد؟
جوابش [tex]O(k\: \lg k)[/tex] هستش.
اگه بصورت عادی حسابش کنیم،که میشه [tex]O(k\: \lg n)[/tex]
ولی نمیدونم که چجور بصورت کارا میشه [tex]O(k\: \lg k)[/tex]

ممنونم میشم اگه کسی بلده،واسم توضیح بده.
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

sixsixsix پاسخ داده:

RE: kمین کوچکترین عنصر در یک هرم کمینه؟

این سوال، قبلا سوال خودم بوده
من توضیح میدم، سعی کن مثالی واسه خودت بزنی خیلی راحت میفهمی

ببین برای اینکار نیاز به یه حافظه کمکی به اندازه k داری وگرنه نمیشه این کار رو انجام داد.
در وهله دوم)
ما یه minheap اولیه داریم که مسلماً میدونیم کوچکترین عنصر آن در ریشه است
بایــد یه minheap دیگه خودمون بسازیم (به اندازه k) ، اسمشو مثلا میذاریم A
توی A باید مینیم عنصرهای مین هیپ اصلی رو قرار بدیم. در ابتدا توی A فقط عنصر ریشه از مین هیپ رو داریم. هر بار از A کوچکترین عنصر رو حذف میکنیم و دو عنصر فرزند آنرا که در مین هیپ اصلی قرار دارند در A اضافه میکنیم. مرتبه این کار برای هر بار logk هست (چون شامل یه حذف از مین هیپ A (به اندازه k) و دو درج در مین هیپ A (به اندازه k) هست که میشه ۳logk=O(logk))
اگه این عمل رو k بار انجام بدیم دقیقا عنصر ریشه مین هیپ A در مرحله k ام جواب است. که هر مرحله logk هست که میشه klogk
نمیدونم متوجه شدی یا نه ، من تو توضیح دادن خیلی ضعیفم ConfusedSmile
سوالی بود بپرس دقیقتر بگم
راستی بگم من این جواب رو قبلا از یکی از ساب سایت های stackoverflow پیدا کردم.
نقل قول این ارسال در یک پاسخ

ارسال:
  

Iranian Wizard پاسخ داده:

RE: kمین کوچکترین عنصر در یک هرم کمینه؟

(۰۸ بهمن ۱۳۹۴ ۰۲:۰۶ ق.ظ)sixsixsix نوشته شده توسط:  این سوال، قبلا سوال خودم بوده
من توضیح میدم، سعی کن مثالی واسه خودت بزنی خیلی راحت میفهمی

ببین برای اینکار نیاز به یه حافظه کمکی به اندازه k داری وگرنه نمیشه این کار رو انجام داد.
در وهله دوم)
ما یه minheap اولیه داریم که مسلماً میدونیم کوچکترین عنصر آن در ریشه است
بایــد یه minheap دیگه خودمون بسازیم (به اندازه k) ، اسمشو مثلا میذاریم A
توی A باید مینیم عنصرهای مین هیپ اصلی رو قرار بدیم. در ابتدا توی A فقط عنصر ریشه از مین هیپ رو داریم. هر بار از A کوچکترین عنصر رو حذف میکنیم و دو عنصر فرزند آنرا که در مین هیپ اصلی قرار دارند در A اضافه میکنیم. مرتبه این کار برای هر بار logk هست (چون شامل یه حذف از مین هیپ A (به اندازه k) و دو درج در مین هیپ A (به اندازه k) هست که میشه ۳logk=O(logk))
اگه این عمل رو k بار انجام بدیم دقیقا عنصر ریشه مین هیپ A در مرحله k ام جواب است. که هر مرحله logk هست که میشه klogk
نمیدونم متوجه شدی یا نه ، من تو توضیح دادن خیلی ضعیفم ConfusedSmile
سوالی بود بپرس دقیقتر بگم
راستی بگم من این جواب رو قبلا از یکی از ساب سایت های stackoverflow پیدا کردم.
بله کاملا متوجه شدمBlush توضیحتون خیلی هم خوب بودBlush
ممنونم از وقتی که گذاشتین.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

molayi پاسخ داده:

RE: kمین کوچکترین عنصر در یک هرم کمینه؟

سلام دوستان اگر کسی میتونه جواب من رو بده چرا جواب این سوال n نمیشه ؟؟؟؟؟؟
میدونیم که هرم داده ساختار اصلیش ارایه است و میتونیم این آرایه رو با روش میانه میانه ها کاامین کوچکترین رو بدست اورد یعنی زمان n!!!!!!!!!
یعنی کلا از هرم کمینه بودن استفاده نکنیم چون سوال میگه بهترین زمان رو بگید!!!!!!!!!!!!!!!!!!!!

زمان n بدتر از k log k هست ؟؟اگر این طور هست که خوب k log k بهتره
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question رسم درخت با ۲۶ گره و ارتفاع کمینه porseshgar ۰ ۱,۵۴۴ ۱۶ بهمن ۱۳۹۷ ۱۲:۱۱ ب.ظ
آخرین ارسال: porseshgar
  محاسبه چندمین عنصر آرایه Mr.R3ZA ۶ ۶,۰۹۴ ۱۹ شهریور ۱۳۹۷ ۰۸:۱۲ ب.ظ
آخرین ارسال: Saman
  تعیین بزرگترین و کوچکترین توان در ممیز شناور؟؟ explorer ۴ ۴,۳۹۵ ۰۱ اردیبهشت ۱۳۹۶ ۰۸:۴۷ ب.ظ
آخرین ارسال: pe.esf
  ۶۰۰ مساله | هرم ها | ۵۸.۳ Happiness.72 ۶ ۳,۷۴۲ ۱۵ اسفند ۱۳۹۵ ۰۵:۲۵ ب.ظ
آخرین ارسال: Happiness.72
  حل سوال ۲ دکتری ۹۶ ( یافتن kامین عنصر ) arash691 ۲ ۲,۲۳۵ ۱۱ اسفند ۱۳۹۵ ۰۲:۲۰ ق.ظ
آخرین ارسال: Saman
  سوال( یافتن اولین و دومین عنصر بیشینه ) arash691 ۰ ۱,۳۳۱ ۰۵ اسفند ۱۳۹۵ ۱۰:۵۶ ب.ظ
آخرین ارسال: arash691
  هرم کامپیوتر ۹۵ Hopegod ۲ ۱,۴۰۴ ۲۵ آذر ۱۳۹۵ ۰۱:۰۳ ب.ظ
آخرین ارسال: Hopegod
  ارتفاع هرم Hopegod ۳ ۱,۹۶۲ ۱۰ آذر ۱۳۹۵ ۰۶:۰۹ ب.ظ
آخرین ارسال: Hopegod
  الگوریتم نزدیک ترین عنصر موجود (ساختمان داده) ememem ۴ ۲,۶۳۹ ۱۱ اردیبهشت ۱۳۹۵ ۱۱:۰۳ ب.ظ
آخرین ارسال: ememem
  مرتبه یافتن k عنصر کوچک آرایه Nesyan ۴ ۲,۷۳۵ ۰۸ اردیبهشت ۱۳۹۵ ۰۴:۱۸ ق.ظ
آخرین ارسال: reza.bsh

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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