سلام.یه سوال داشتم.
kمین کوچکترین عنصر در یک هرم کمینه n عنصری رو بصورت کارا با چه مرتبه ای میشه پیدا کرد؟
جوابش [tex]O(k\: \lg k)[/tex] هستش.
اگه بصورت عادی حسابش کنیم،که میشه [tex]O(k\: \lg n)[/tex]
ولی نمیدونم که چجور بصورت کارا میشه [tex]O(k\: \lg k)[/tex]
ممنونم میشم اگه کسی بلده،واسم توضیح بده.
این سوال، قبلا سوال خودم بوده
من توضیح میدم، سعی کن مثالی واسه خودت بزنی خیلی راحت میفهمی
ببین برای اینکار نیاز به یه حافظه کمکی به اندازه k داری وگرنه نمیشه این کار رو انجام داد.
در وهله دوم)
ما یه minheap اولیه داریم که مسلماً میدونیم کوچکترین عنصر آن در ریشه است
بایــد یه minheap دیگه خودمون بسازیم (به اندازه k) ، اسمشو مثلا میذاریم A
توی A باید مینیم عنصرهای مین هیپ اصلی رو قرار بدیم. در ابتدا توی A فقط عنصر ریشه از مین هیپ رو داریم. هر بار از A کوچکترین عنصر رو حذف میکنیم و دو عنصر فرزند آنرا که در مین هیپ اصلی قرار دارند در A اضافه میکنیم. مرتبه این کار برای هر بار logk هست (چون شامل یه حذف از مین هیپ A (به اندازه k) و دو درج در مین هیپ A (به اندازه k) هست که میشه ۳logk=O(logk))
اگه این عمل رو k بار انجام بدیم دقیقا عنصر ریشه مین هیپ A در مرحله k ام جواب است. که هر مرحله logk هست که میشه klogk
نمیدونم متوجه شدی یا نه ، من تو توضیح دادن خیلی ضعیفم
سوالی بود بپرس دقیقتر بگم
راستی بگم من این جواب رو قبلا از یکی از ساب سایت های stackoverflow پیدا کردم.
(۰۸ بهمن ۱۳۹۴ ۰۲:۰۶ ق.ظ)sixsixsix نوشته شده توسط: این سوال، قبلا سوال خودم بودهبله کاملا متوجه شدم
من توضیح میدم، سعی کن مثالی واسه خودت بزنی خیلی راحت میفهمی
ببین برای اینکار نیاز به یه حافظه کمکی به اندازه k داری وگرنه نمیشه این کار رو انجام داد.
در وهله دوم)
ما یه minheap اولیه داریم که مسلماً میدونیم کوچکترین عنصر آن در ریشه است
بایــد یه minheap دیگه خودمون بسازیم (به اندازه k) ، اسمشو مثلا میذاریم A
توی A باید مینیم عنصرهای مین هیپ اصلی رو قرار بدیم. در ابتدا توی A فقط عنصر ریشه از مین هیپ رو داریم. هر بار از A کوچکترین عنصر رو حذف میکنیم و دو عنصر فرزند آنرا که در مین هیپ اصلی قرار دارند در A اضافه میکنیم. مرتبه این کار برای هر بار logk هست (چون شامل یه حذف از مین هیپ A (به اندازه k) و دو درج در مین هیپ A (به اندازه k) هست که میشه ۳logk=O(logk))
اگه این عمل رو k بار انجام بدیم دقیقا عنصر ریشه مین هیپ A در مرحله k ام جواب است. که هر مرحله logk هست که میشه klogk
نمیدونم متوجه شدی یا نه ، من تو توضیح دادن خیلی ضعیفم
سوالی بود بپرس دقیقتر بگم
راستی بگم من این جواب رو قبلا از یکی از ساب سایت های stackoverflow پیدا کردم.
توضیحتون خیلی هم خوب بودممنونم از وقتی که گذاشتین.
سلام دوستان اگر کسی میتونه جواب من رو بده چرا جواب این سوال n نمیشه ؟؟؟؟؟؟
میدونیم که هرم داده ساختار اصلیش ارایه است و میتونیم این آرایه رو با روش میانه میانه ها کاامین کوچکترین رو بدست اورد یعنی زمان n!!!!!!!!!
یعنی کلا از هرم کمینه بودن استفاده نکنیم چون سوال میگه بهترین زمان رو بگید!!!!!!!!!!!!!!!!!!!!
زمان n بدتر از k log k هست ؟؟اگر این طور هست که خوب k log k بهتره