بچه ها میشه لطفا یه نگاه به این سوالا بندازید بینهایت ممنون میشم..
سمت چپی میشه ۳
سمت راستی میشه ۲
سوال دو گزینه ۳ میشه!
سرعت درج از کند به سریع
آرایه مرتب(n)>لیست> BST مرتبه lgn
(آرایه نامرتب و هش هم که طبق صورت سوال از رده خارج اند)
(۱۱ بهمن ۱۳۹۱ ۰۱:۲۹ ب.ظ)۸Operation نوشته شده توسط: سوال دو گزینه ۳ میشه!
سرعت درج از کند به سریع
آرایه مرتب(n)>لیست> BST مرتبه nlgn
(آرایه نامرتب و هش هم که طبق صورت سوال از رده خارج اند)
بله حواسم نبود ببخشید، چرا BST سریع تره مگه درج در لیست پیوندی O(n) نیست؟
اون سوالم عوض کردم اگه میشه یه نگاه بهش بندازید
(۱۱ بهمن ۱۳۹۱ ۰۱:۵۱ ب.ظ)avril22 نوشته شده توسط: چرا BST سریع تره مگه درج در لیست پیوندی O(n) نیست؟ببشخید حواسم نبود یه n زیادی نوشتم!
خب lgn کمتر از n هستش دیگه!(البته در حالت میانگین BST)
در مورد سوال ادغام پارسه گفته گزینه ۳ اما کلید سنجش گزینه دو هستش! من هم با کلید سنجش موافقم
در واقع کافیه دوتا mHeap رسم کنید و بعد تنها دوتا ریشه اونها رو در مرتبه عدد بزرگتر که عدد n هستش با مرتبه lgn با هم مقایسه کنید.(باید توجه کنید که نیازی نیست که بقیه عناصر دو هیپ باهم ادغام بشه!تنها همین ریشه کفایت می کنه!)
بعد یه هیپ ادغام شده داریم. که ممکنه کامل نباشه! و برای تبدیل شدن اون به یه هیپ(شرط کامل بودن درخت منظورمه) در مرتبه
[tex]lg(n m)=lgn [/tex] عمل هپپیفای رو انجام میدیم.
البته طبق این حل من خودم با نحوه حل سوال مشابه علوم که گذاشته بودید مشکل دارم!
آهان من همینو نمیدونستم که باید حالت میانگین رو در نظر بگیریم
مرسی دومی هم متوجه شدم..حالا چرا اون سوال علوم کامپیوتر رو از این راه نرفت این که خیلی راحتره..شاید اون راه با آرایست ،اما اینجا گفته به شکل درخت، اما اونم آسونه اگه متوجه نشدین بگید توضیح بدم...ممنونم
(۱۱ بهمن ۱۳۹۱ ۰۷:۳۶ ب.ظ)avril22 نوشته شده توسط: اما اینجا گفته به شکل درخت، اما اونم آسونه اگه متوجه نشدین بگید توضیح بدم...ممنونمآره ممنون میشم توضیح بدید!آخه ساختمان داده جفتشون آرایست!درخت رو که نمیشه بدون ساختمان داده در نظر گرفت!
بله درست میگید من دیگه مخم قفل کرده
بله خواهش میکنم ۲تا minheap داریم یکی به تعداد n و یکی به تعداد m فرض میکنیم می خوایم اون که تعدادش mتا هست رو دونه دونه حذف کنیم(logm میشه وچون mبار تکرار میشه mlogm) و توی اون یکی درج کنیم(درج توی این logn میشه و چون mبار انجام میشهmlogn)
mlogm+mlogn=m(logm+logn)=mlogmn
اگه جاییش واضح نبود بگید توضیح بدم ..
(۱۱ بهمن ۱۳۹۱ ۰۹:۲۵ ب.ظ)avril22 نوشته شده توسط: اگه جاییش واضح نبود بگید توضیح بدم ..نه عالی بود قبلا روش دقت نکرده بودم
مرسی
من این ادغام هیپ رو قاطی کردم ؟ اینجا تو شکل سمت راستی گفتین log n
توی پوران گفته تتا n
توی ازمون سنجش هم سوال داده بود دو درخت هیپ هر کدوم با n عنصر در زمان ۲n ادغام می شن ؟
کدوم درستن
خواهشا منو از این قاطی شدن در بیارین
دوستان این سوالم نگاه کنید
ممنون