حل تشریحی سوال شماره 70 طراحی الگوریتم
کنکور ارشد مهندسی کامپیوتر 1401
ارایه A شامل n عنصر داده شده است. عنصری از ارایه که حداقل بار تکرار شده باشد را یک عضو پرتکرار می نامیم. میخواهیم در ارایه A یک عضو پرتکرار را در صورت وجود پیدا کنیم. برای اینکار از یک روش مستقیم و غلبه به این صورت استفاده میکنیم: ابتدا ارایه را به سه قیمت با اندازه برابر تقسیم میکنیم و در هر کدام از قسمت ها بطور بازگشتی در صورت وجود یک عضو پرتکرار را پیدا میکنیم. سپس میزان تکرار هر کدام از این سه عضو پرتکرار را در ارایه اصلی جستجو میکنیم و در صورتی که میزان تکرار هر عضو حداقل بود ان عضو را به عنوان عضو پرتکرار برمیگردانیم. کدام گزاره در خصوص این الگوریتم درست است؟ ( فرض کنید n توانی از 3 است.)
زمان اجرا O(n log n) است، اما الگوریتم لزوما درست کار نمیکند.
زمان اجرا O(n log n) است و الگوریتم درست کار میکند.
زمان اجرا O(n) است، اما الگوریتم لزوما درست کار نمیکند.
زمان اجرا O(n) است و الگوریتم درست کار میکند.