بزرگ ترین عنصر یک آرایه نامرتب

[zahra_zapata]

با استفاده از روش تقسیم و غلبه ، بزرگ ترین عنصر یک آرایه نامرتب را پیدا کنید.

[Developer Programmer]

سلام
تا جایی که حقیر میدونم، روش تقسیم و حل واسه داده های مرتب معنی داره،
یعنی اگه آرایه ای مرتب نشده باشه نمی تونین بفهمین ، جستجو رو سمت راست ادامه بدین یا سمت چپ

[Developer Programmer]

خیلی وقته که این سوالتون ذهنم رو مشغول کرده بود
جواب خیلی راحته ؛ کافیه الگوریتم MergeSort رو کمی دستکاری کنید و اگه خیلی خوب جلو برید
تعداد مقایسه ها 3n/2 -2 میشه و اگه اشتباه نکنم پیچیدگی اگوریتم هم n میشه.

[someCoder]

روش تقسیم و حل واسه داده های مرتب معنی داره،
یعنی اگه آرایه ای مرتب نشده باشه نمی تونین بفهمین ، جستجو رو سمت راست ادامه بدین یا سمت چپاون که شما میگین Binary search هست و این یه چیز دیگه! کی گفته با D&C نمیشه؟؟؟

سوال ترم قبل بوده و تقریباکسی جواب نداده.جدا؟ یعنی اینقدر سخته؟؟؟

جواب خیلی راحته ؛ کافیه الگوریتم MergeSort رو کمی دستکاری کنید و اگه خیلی خوب جلو برید
تعداد مقایسه ها 3n/2 -2 میشه و اگه اشتباه نکنم پیچیدگی اگوریتم هم n میشه.
پیچیدگی که 100% از درجه n هست! چون راه معمولیش با این Order جواب میده! در حقیقت اینجا Order فرق نمیکنه! فقط Overhead کم میشه! جواب هم همونطور که گفتید 3n/2 -2 هست.

[rahnama66]

انجام این برنامه خیلی راحته بوسیله درخت تورنمنت به این صورت که سایز آرایه را 2 برابر تعداد اعداد میگیریم از آخر شروع به پر کردن مکنیم به اینصورت که مقدار هر خانه با خانه قبلش مقایسه شود و حاصل کوچکترین یا بزرگتین ثبت شود و این درخت تا آخر ادامه یابد که آخرین عنصری که باقی میماند یعنی عنصر اول آرایه برابر میشود با بزرگترین یا کوچکترین :چشمک: