پاورپوینت روش تقسيم و حل Divide and Conqure

شامل 37 اسلاید درقالب پاورپوینت و قابل ویرایش

فهرست برخی از مطالب:

روش تقسيم و حل Divide and Conqure

زمان محاسبه تابع DAndC

جستجوی دودويی

الگوريتم binary search

تحليل پيچيدگی زمانی الگوريتم binary search

Merge sort

مرتب سازی ادغامی

الگوريتم مرتب سازی ادغامی

الگوريتم ادغام

تحليل پيچيدگی زمانی الگوريتم mergesort

تحليل پيچيدگی فضا الگوريتم mergesort

الگوريتم دوم مرتب سازی ادغامی (با صرفه جویی در فضا:n)

مرتب سازی سریع Quicksort

الگوریتم Quicksort

روال تقسیم برای زیرآرایه A[p..r]

اجرای روال partition

تحلیل پیچیدگی زمان برای quicksort

اثبات درستی رابطه بدست آمده:

تحلیل پیچیدگی حالت میانی الگوریتم quicksort

و... .

بخشی از متن فایل پاورپوینت:

• يک نمونه از مسأله را به دو يا چند قسمت کوچکتر تقسيم ميکند که معمولا نمونه هايی از مسأله اصلی هستند. اگر جواب مسأله های کوچکتر به راحتی محاسبه شود, می توان جواب نمونه اصلی را با ترکيب اين جوابها به دست آورد, در غير اين صورت ميتوان آنها را به نمونه های کوچکتر تقسيم کرد .
• يک روش بالا به پايين است.

Algorithm DAndC(P)

{ if Small(P) return Solve(P);

else

{ divide P into smaller instances P₁,P₂,…,P_k, k>=1;

Apply DAndC to each of these subproblems;

return Combine(DAndC(P₁),DAndC(P₂),…,DAndC(P_k);

}

}