صفحه محصول - پاورپوینت طراحی الگوریتم ها فصل چهارم تقسم و حل

پاورپوینت طراحی الگوریتم ها فصل چهارم تقسم و حل (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 مي‌باشند.