سلام دوستان سوال موجود توی عکس رو ک مربوط به سال ۹۲ هست می تونید اگه راه حلشو بلدید برام توضیح بدید؟ با تشکر
راستی من نمیدونم چطور اینجا فرمول ریاضی تایپ کنم اگه راهنمایی گنید ممنون می شم
با تشکر
سلام،
این سوال مشابه سوال آی تی سال ۹۵ هست که اونجا فقط نحوه بیان رو تغییر داده
شما هر زیر مجموعه از آرایه n عنصری رو با هر نامی بگیرید توی این آرایه میاید سرچ میکنید که ببینید آیا عنصر مورد نظر شما در اون آرایه هستش که مینیمم باشه یا خیر
عنصر مینیمم به احتمال یک بر i در خانه اول یا دوم یا سوم یا iام قرار داره(سطر چهار الگوریتم داده شده بررسی این هست)، مجموع این احتمالات میشه ln n که همیشه ازمرتبه لگاریتمی هستش،گزینه ۱ پاسخه
اشتباه رایج در این نوع مرتب سازی که منجر به انتخاب گزینه ۲ میشود میانه گیری هست، یعنی فرض رو بر این بگذاریم که در هر جایگشت از زیر مجموعه ها میانه بگیریم و در نهایت میانه میانه ها، یا پارتیشن بزنیم و kامین کوچکترین عنصر رو در زمان n بدست بیاریم.(البته به نظر من)
یه چیزدیگه اینکه :
سوال رو در جای درست بپرسید
سپاسگزارم
خیلی ممنون از پاسختون