پاورپوینت طراحی الگوریتم ها فصل چهارم تقسم و حل (pptx) 45 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 45 اسلاید
قسمتی از متن PowerPoint (.pptx) :
1
فصل چهارم
تقسم و حل
2
Computer algorithms
مساله مرتب سازی ادغام
مساله مرتب سازی سریع
مساله ضرب ماتریس استراسن
week7
حل مسأله مرتب‌سازي ادغام به روش تقسيم و حل
فرض كنيد ليست نامرتبي با n عنصر داريم كه مي‌خواهيم اين ليست را به ترتيب صعودي مرتب كنيم.
در عمل combine هم مرتب سازی و هم ترکیب صورت می گیرد
week7
ليست زير را با استفاده از الگوريتم merge sort مرتب كنيد
حل: ابتدا ليست اعداد را به صورت زير در آرايه‌اي قرار مي‌دهيم:
Left
Right
week7
الف) براي مرتب كردن ليست فوق درخت فراخواني‌هاي تابع mergesort به صورت زير مي‌باشد:
تعداد كل فراخواني‌ها برابر با تعداد small (p) ها + تعداد merge ها يعني 10 + 9 = 19 مي باشد.
تعداد فراخواني بازگشتي برابر 18 است .
10
week7
دومين مقايسه در آخرين merge انجام شده ، مقايسه (285 , 254) مي‌باشد.
اولين مقايسه در آخرين merge انجام شده، مقايسه (179 , 254) مي‌باشد.
week7
پيچيدگي الگوريتم merge sort
week7
حل مسأله مرتب‌سازي سريع به روش تقسيم و حل
☺به عنوان مثال فرض كنيد آرايه حاوي عناصر زير باشد. نحوه عمل مرتب‌سازي سريع را نشان مي‌دهيم:
1- ابتدا محل واقعی عنصر اول یعنی 15 را در لیست مرتب مشخص میکنیم:
week7
الگوريتم Quick Sort
فرض كنيد آرايه اي با نام a داريم كه تعداد عناصر آن n مي باشد و مي خواهيم اين عناصر را به ترتيب صعودي مرتب كنيم.
براي اينكار مي‌توان از الگوريتم زير استفاده نمود:
مقایسه ها در تابع partition انجام می شود و در ضمن تابع combine هم نداریم
وظيفه تابع partition پيدا كردن انديس عنصري مانند K است كه تمام عناصر قبل از آن
كوچكتر از K و تمام عناصر بعد از آن بزرگتر از K مي‌باشند.
