با استفاده از روش تقسیم و غلبه ، بزرگ ترین عنصر یک آرایه نامرتب را پیدا کنید.
Printable View
با استفاده از روش تقسیم و غلبه ، بزرگ ترین عنصر یک آرایه نامرتب را پیدا کنید.
سلام
تا جایی که حقیر میدونم، روش تقسیم و حل واسه داده های مرتب معنی داره،
یعنی اگه آرایه ای مرتب نشده باشه نمی تونین بفهمین ، جستجو رو سمت راست ادامه بدین یا سمت چپ
خیلی وقته که این سوالتون ذهنم رو مشغول کرده بود
جواب خیلی راحته ؛ کافیه الگوریتم MergeSort رو کمی دستکاری کنید و اگه خیلی خوب جلو برید
تعداد مقایسه ها 3n/2 -2 میشه و اگه اشتباه نکنم پیچیدگی اگوریتم هم n میشه.
اون که شما میگین Binary search هست و این یه چیز دیگه! کی گفته با D&C نمیشه؟؟؟نقل قول:
روش تقسیم و حل واسه داده های مرتب معنی داره،
یعنی اگه آرایه ای مرتب نشده باشه نمی تونین بفهمین ، جستجو رو سمت راست ادامه بدین یا سمت چپ
جدا؟ یعنی اینقدر سخته؟؟؟نقل قول:
سوال ترم قبل بوده و تقریباکسی جواب نداده.
پیچیدگی که 100% از درجه n هست! چون راه معمولیش با این Order جواب میده! در حقیقت اینجا Order فرق نمیکنه! فقط Overhead کم میشه! جواب هم همونطور که گفتید 3n/2 -2 هست.نقل قول:
جواب خیلی راحته ؛ کافیه الگوریتم MergeSort رو کمی دستکاری کنید و اگه خیلی خوب جلو برید
تعداد مقایسه ها 3n/2 -2 میشه و اگه اشتباه نکنم پیچیدگی اگوریتم هم n میشه.
انجام این برنامه خیلی راحته بوسیله درخت تورنمنت به این صورت که سایز آرایه را 2 برابر تعداد اعداد میگیریم از آخر شروع به پر کردن مکنیم به اینصورت که مقدار هر خانه با خانه قبلش مقایسه شود و حاصل کوچکترین یا بزرگتین ثبت شود و این درخت تا آخر ادامه یابد که آخرین عنصری که باقی میماند یعنی عنصر اول آرایه برابر میشود با بزرگترین یا کوچکترین :چشمک: