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