کسی میدونه چرا جوابش شده log n
مرتب سازیش که میشه از مرتبه ی n پس کلا میشه از مرتبه ی n.
فکر میکنم جوابش قبلا داده شده بود.
یه کم در طرح سوال عجله کردم.
با عرض پوزش
فرض کنین که دو آرایه داریم می خوایم k امین عنصر رو پیدا کنیم این دو آرایه A و B هستند.
نکته ی اول : چون دو آرایه مرتب هستن پس k امین عنصر حتما در بین عناصر ۱ تا k آرایه ی A یا عناصر ۱ تا k آرایه ی B هستند.
خب اینجا پس عناصری که باید عنصر مورد نظر رو در اون پیدا کنیم به ۲k عنصر محدود می شن.
نکته ی دوم : اینجا ما ۲k عنصر داریم . پس k امین عنصر در واقع k امین عنصر این ۲k یعنی میانه ی این عناصر هست.
-----
بدترین حالت اجرای الگوریتم فوق بدترین حالت k است. که یعنی lgn هست.
-------------
این تست اینجا بحث شده قبلا :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.