با عرض سلام
دوستان سوال زیر یکی از تقریبا سوال های پر تکرار کنکور هست. فکر کنم یک راه حلش این هست
که هر عنصر رو به صورت یکتا در یک درخت جست و جوی دودویی وارد کنیم. چون k عنصر متمایز در درخت وارد می شود پس تعداد سطوح درخت متعادل از مرتبه ی log (k) هست و چون عمل درج برای n عنصر بررسی می شه ( برای عناصری که تکراری هستند این عمل صرف جست و جوی عنصر می شه ) پس در کل هزینه ی ساخت درخت از مرتبه ی [tex]\Theta\: (n.\log k)[/tex] هست. درست می گم. خوشحال می شم نظرات شما دوستان گرامی رو هم بشنوم
با تشکر
سلام و وقت بخیر ...
در مورد سوال هایی که عنوان کردید بحث و گمانه زنی زیاد است ....
که در یکی از پست ها به طور کامل بحث شده در مورد آن
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که توصیه میکنم بررسی کنید ..
اما نکته ای که است این میباشد که در مورد سوال اول میتوان اعداد را یکی یکی در یک درخت جستجوی دودویی متوازن وارد کرد که در نهایت تعداد نود های این درخت برابر k خواهد بود و ما n بار قصد وارد کردن عنصر در درخت را داریم ( ولی فقط k بار از این n بار موفق است ) هزینه انجام شده برابر با [tex]O(nlogk)[/tex] است که شما هم اشاره کردید . حال باید این درخت که دارای k عنصر است را پیمایش میان ترتیب کنیم که هزینه این عمل خطی است . در انتها باید تعداد تکرار های هر عدد را هم داشته باشیم ( این کار هم با درهم سازی امکان پذیر است و هم روش های دیگر ... ) که مرتبه خطی دارد ... با توجه به گزینه ها همین گزینه دوم مناسب تر است . نکته مهم این است که زمانی در بدترین حالت به این مرتبه میرسیم که درخت جستجوی دودویی متوازن باشد ( مانند درخت AVL )
(۲۷ فروردین ۱۳۹۶ ۰۳:۲۳ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر ...
در مورد سوال هایی که عنوان کردید بحث و گمانه زنی زیاد است ....
که در یکی از پست ها به طور کامل بحث شده در مورد آن
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که توصیه میکنم بررسی کنید ..
اما نکته ای که است این میباشد که در مورد سوال اول میتوان اعداد را یکی یکی در یک درخت جستجوی دودویی متوازن وارد کرد که در نهایت تعداد نود های این درخت برابر k خواهد بود و ما n بار قصد وارد کردن عنصر در درخت را داریم ( ولی فقط k بار از این n بار موفق است ) هزینه انجام شده برابر با [tex]O(nlogk)[/tex] است که شما هم اشاره کردید . حال باید این درخت که دارای k عنصر است را پیمایش میان ترتیب کنیم که هزینه این عمل خطی است . در انتها باید تعداد تکرار های هر عدد را هم داشته باشیم ( این کار هم با درهم سازی امکان پذیر است و هم روش های دیگر ... ) که مرتبه خطی دارد ... با توجه به گزینه ها همین گزینه دوم مناسب تر است . نکته مهم این است که زمانی در بدترین حالت به این مرتبه میرسیم که درخت جستجوی دودویی متوازن باشد ( مانند درخت AVL )
بسیار سپاسگزارم دوست گرامی
شاد و موفق باشید
(۲۷ فروردین ۱۳۹۶ ۰۳:۲۳ ب.ظ)alireza01 نوشته شده توسط: سلام و وقت بخیر ...با سپاس از شما دوست گرامی
در مورد سوال هایی که عنوان کردید بحث و گمانه زنی زیاد است ....
که در یکی از پست ها به طور کامل بحث شده در مورد آن
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که توصیه میکنم بررسی کنید ..
اما نکته ای که است این میباشد که در مورد سوال اول میتوان اعداد را یکی یکی در یک درخت جستجوی دودویی متوازن وارد کرد که در نهایت تعداد نود های این درخت برابر k خواهد بود و ما n بار قصد وارد کردن عنصر در درخت را داریم ( ولی فقط k بار از این n بار موفق است ) هزینه انجام شده برابر با [tex]O(nlogk)[/tex] است که شما هم اشاره کردید . حال باید این درخت که دارای k عنصر است را پیمایش میان ترتیب کنیم که هزینه این عمل خطی است . در انتها باید تعداد تکرار های هر عدد را هم داشته باشیم ( این کار هم با درهم سازی امکان پذیر است و هم روش های دیگر ... ) که مرتبه خطی دارد ... با توجه به گزینه ها همین گزینه دوم مناسب تر است . نکته مهم این است که زمانی در بدترین حالت به این مرتبه میرسیم که درخت جستجوی دودویی متوازن باشد ( مانند درخت AVL )
فقط محض اطلاع در ۶۰۰ مسئله قدسی (سوال ۱۲۰/۲) هم تست مشابهی با این تست ها وجود دارد