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

دسته بندي : پاورپوینت » گوناگون
نوع فایل.ppt: (قابل ويرايش و آماده پرينت)
تعداد اسلاید : 37 اسلاید

قسمتی از متن.ppt:

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

زمان محاسبه تابع DAndC
T(n)= g(n) کوچک باشد n
T(n1)+ T(n2)+…+ T(nk)+f(n) درغيراينصورت

g(n): زمان لازم برای محاسبه مستقيم پاسخ برای ورودی های کوچک
: f(n) زمان لازم برای تقسيم مسأله و ترکيب راه حلها
معمولا:
T(n)= T(1) n=1
aT(n/b)+f(n) n>1

جستجوی دودويی
مسأله: تعيين اين که آيا x در آرايه مرتب s با اندازه n وجود دارد يا خير.
مثال:n=14
-15,-6,0,7,9,23,54,82,101,112,125,131,142,151
x=9
low high mid s[mid]
1 14 7 54
1 6 3 0
4 6 5 9 found
x=-14
low high mid s[mid]
1 14 7 54
1 6 3 0
1 2 1 -15
2 2 2 -6
2 1 not found

الگوريتم binary search
int binsearch(int low,int high)
{ int mid;
if (low > high) return 0;
else
{ mid=[(low+high)/2]; عملگر مبنايی
if (x==s[mid])
return mid;
else if(x s[i]
فرض: n=2k
W(n)=W(n/2)+1 n>1
W(1)=1
حل معادله بازگشتی:
W(n)=lg n+1 θ(lg n)
بهترين حالت برای جستجوی موفق: B(n)=c θ(1)
Merge sort

مراحل مرتب سازی ادغامی برای آرايه ای با n عنصر:
1. تقسيم آرايه به دو زير آرايه هريک با n/2 عضو
2. حل هر زير آرايه با مرتب کردن آن. اگر آرايه به اندازه کافی کوچک نباشد, از بازگشت برای انجام اين کار استفاده می کنيم.
3. ادغام زير آرايه های مرتب شده
مرتب سازی ادغامی
مرحله تقسيم:
310,285,179,652,351,423,861,254,450,520
310,285,179,652,351 423,861,254,450,520
310,285 179,652,351 423,861 254,450,520
310 285 179 652,351 423 861 254 450,520
310 285 179 652 351 423 861 254 450 520

مرحله ادغام:
285,310 179 351,652 423,861 254 450,520
285,310 179,351,652 423,861 254,450,520
179,285,310,351,652 254,423, 450, 520,861
179, 254,285,310,351,423, 450, 520,652,861
الگوريتم مرتب سازی ادغامی
void mergesort(int n, key s[])
{ int h=[n/2],m=n-h;
key u[1..h],v[1..m];
if (n>1)
{ copy s[1..h] to u[1..h];
copy s[h+1..n] to v[1..m];
mergesort(h,u);
mergesort(m,v);
merge(h,m,u,v,s)
}
}

الگوريتم ادغام
void merge(int h,int m,key u[],key v[],key s[])
{ int i=1,j=1,k=1;
while(i h) copy v[i..m] to s[k..h+m];
else copy u[j..h] to s[k..h+m];
}
تحليل پيچيدگی زمانی الگوريتم mergesort
در بدترين حالت برای الگوريتم merge: W(h,m)=h+m-1
در الگوريتم mergesort :
W(n)=W(h)+W(m)+h+m-1

زمان ادغام زمان مرتب سازی v زمان مرتب سازی u
W(n)=W[n/2]+W[n/2]+n-1=2W(n/2)+n-1 n>1
W(1)=0
حل رابطه بازگشتی: a=2, b=2, k=1 2=21
W(n)θ(nlog2n)