(۰۲ اسفند ۱۳۹۱ ۱۱:۲۴ ب.ظ)mehdi.nine نوشته شده توسط: (02 اسفند ۱۳۹۱ ۰۸:۴۲ ب.ظ)alireza.ghp نوشته شده توسط:
نه همون ۲ درسته .
بچه ها واسه سوال ۴۵ کسی مشکل نداره؟ این لیکو ببینید لطفا:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال ۴۲ کسی راه حلی واسه گزینه ۲ داره؟
من واسه گزینه ۳ دارم!
لطفا اگه کسی چیزی می دونه بگه که من درخواست بی خود به سایت سنجش ندم.
با سپاس.
دوست عزیز من این سوال رو بر اساس جزوه دکتر حاج سید جوادی حل کردم که از نظر من کلید سنجش غلطه اگه شما جواب بهتری سراغ ندارید حتما اعتراض کنیم
سوال ۴۲ بخش اول : S1=(1,2,……,k)
در آرایه نامرتبA ابتدا توسط الگوریتمselection - کامین کوچکترین عنصر(k)را با مرتبه (O(n یافته وبا محور قرار دادن آن آرایه را پارتیشن میکنیم(O(n)) ,حال kعنصر کوچکتر آرایه در ابتدای آرایه به صورت نامرتب قرار دارد که توسط quick sortآنرا با مرتبه O(klogk) مرتب میکنیم . که این kعنصر مرتب ابتدای آرایه همان جواب مسئله است پس در کل داریم : O(n+klogk)
بخش دوم : S2=(n/2,n/4,n/8,……,۱)
ابتدا میانه (n/2امین کوچکترین عنصر)را با مرتبه O(n)یافته و براساس آن آرایه را پارتیشن میکنیم حال از ۱ تا n/2امین عنصر به صورت نامرتب در ابتدای آرایه قرار دارند که آنرا توسط quick sort با مرتبه O(nlogn)مرتب میکنیم حال در این بخش مرتب شده با جستجوی باینری با مرتبه lognعناصر S2 را بدست می آوریم . پس در کل داریم: O(n+nlogn+logn)=O(nlogn)
پس جواب این سوال : S1در O(n+klogk) و S2در O(nlogn