X
تبلیغات
مقالات و جزوه های درسی رشته کامپیوتر - طراحی الگوریتم ها جلسه دوم

 


فصل دوم:

روش تقسیم و حل

 

 

روش تقسیم و حل یک روش بالا به پایین است.

 

حل یک نمونه سطح بالای مسئله با رفتن به جزء و بدست آوردن حل نمونه های کوچکتر حاصل می شود.

هنگام پی ریزی یک الگوریتم بازگشتی ، باید:

1- راهی برای به دست آوردن حل یک نمونه از روی حل یک نمونه ازروی حل یک یا چند نمونه کوچک تر طراحی کنیم.

2- شرط(شرایط ) نهایی نزدیک شدن به نمونه(های) کوچک تر را تعیین کنیم.

3- حل را در حالت شرط (شرایط)نهایی تعیین کنیم.

 

الگوریتم1-2: جست و جوی دودویی (بازگشتی)

index location ( index low, index high )

{

 index mid;

 if (low > high )

 return 0;

 else {

 mid = Į (low + high) /2⌡;

 if (x = = S [mid])

 return mid;

 else if ( x < S [mid])

 return location (low , mid – 1);

 else

 return location (mid + 1, high);

 }

 }

 

تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم جست و جوی دودویی بازگشتی

عمل اصلی: مقایسه x با S [mid].

 اندازه ورودی: n ، تعداد عناصر آرایه.

W (n) = W (n / 2) + 1

 

 برای n >1 ، n توانی از 2 است W (n) = W (n / 2) + 1

 W (1) = 1

 

 W (n) = Į lg n ⌡+ 1 Є θ (lg n)

 

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

 

ادغام یک فرآیند مرتبط با مرتب سازی است.

 

ادغام دوطرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایه ی مرتب است.

مرتب سازی ادغامی شامل مراحل زیر می شود:

1- تقسیم آرایه به دو زیر آرایه، هر یک با n/2 عنصر.

2- حل هر زیر آرایه با مرتب سازی آن.

3- ترکیب حل های زیر آرایه ها از طریق ادغام آن ها در یک آرایه مرتب.

 

الگوریتم2-2: مرتب سازی ادغامی

 void mergsort (int n , keytype S [ ])

 {

 const int h = Į n/2 ⌡ , m = n – h;

 keytype U [1...h],V [1..m];

 if (n >1) {

 copy S[1] through S[h] to U[h];

 copy S [h + 1] through S[h] to V[1] through V[m];

  mergesort(h, U);

 mergesort(m,V);

 merge (h , m , U,V,S);

 }

 }

الگوریتم3-2: ادغام

 

 void merg ( int h , int m, const keytype U[ ],

 const keytype V[ ],  

 keytype S[ ] )

 {

 index i , j , k;

 i = 1; j = 1 ; k = 1;

 while (i <= h && j <= m) {

 if (U [i] < V [j]) {

 S [k] = U [i]

  i+ + ;

 }

 else {

 S [k] = V [j];

 j+ +;

 }

 k+ +;

 }

 if ( i > h)

 copy V [j] through V [m] to S [k] through S [ h + m ]

 else

 copy U [i] through U [h] to S [k] through S [ h + m ]

 }

تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم 3-2(ادغام)

 

 عمل اصلی: مقایسهU [i] با . V[j]

 اندازه ورودی:h  وm ،تعداد عناصر موجود در هر یک از دو آرایه ورودی.

 

W ( h , m) = h + m - 1

تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم 2-2( مرتب سازی ادغامی)

 

 

عمل اصلی: مقایسه ای که درادغام صورت می پذیرد.

اندازه ورودی: n ، تعداد عناصر آرایه S.

 W (n) = W (h) + W ( m) + h + m – 1

 ↓            ↓             ↓                     

(زمان لازم برای ادغام)     ( زمان لازم برای مرتب سازی  (V    (زمان لازم برای مرتب سازی  (U

 

 برای n >1 که n توانی از 2 است W (n) = 2 W( n / 2) + n -1

 W (1) = 0

W( n ) Є θ ( n lg n)

 

الگوریتم4-2: مرتب سازی ادغامی 2(mergesort 2 )

void mergesort2 (index low, index high)

 {

 index mid;

 if (low < high) {

 mid = Į ( low + high) / 2 ⌡;

 mergesort 2 (low, mid);

 mergesort 2 (mid +1, high);

 merge2(low,mid,high)

 }

  }

 

الگوریتم5-2:ادغام2

مسئله: ادغام دو آرایه ی مرتب S  که درmergesort ایجاد شده اند.

 

 void mrge2 (index low, index mid, index high)

 {

 index i, j , k;

 keytype U [ low..high]

 i = low; j = mid +1 ; k = low;

 while ( i <= mid && j <= high) {

 if ( S [i] < S [j] ) {

 U [k] = S [i];

 i + + ;

 }

 else {

 U [k] = S [j]

 j ++;

 }

 k ++;

 }

 if ( i > mid )

 move S [j] through S [high] to U [k] through U [high]

 else

 move S [i] through S [mid] to U [k] through U [high]

 move U [low] through U [high] to S [low] through S [high]

 }

 

3-2روش تقسیم و حل

 راهبرد طراحی تقسیم و حل شامل مراحل زیر است:

1- تقسیم نمونه ای ازیک مسئله به یک یا چند نمونه کوچکتر.

2- حل هر نمونه کوچکتر. اگر نمونه های کوچک تر به قدر کوچک تر به قدر کافی کوچک نبودند، برای این منظور از بازگشت استفاده کنید.

3- در صورت نیاز، حل نمونه های کوچک تر را ترکیب کنید تا حل نمونه اولیه به دست آید.

 

4-2 مرتب سازی سریع (quicksort)

 

در مرتب سازی سریع، ترتیب آنها از چگونگی افراز آرایه ها ناشی می شود.

 

همه عناصر کوچک تر آز عنصر محوری در طرف چپ آن وهمه عناصربزرگ تر، درطرف راست آن واقع هستند.

 

 

مرتب سازی سریع، به طور بازگشتی فراخوانی می شود تاهر یک از دوآرایه را مرتب کند، آن ها نیز افراز می شوند واین روال ادامه می یابد تا به آرایه ای با یک عنصربرسیم. چنین آرایه ای ذاتاً مرتب است.

 

الگوریتم6-2 :مرتب سازی سریع

مسئله: مرتب سازی n کلید با ترتیب غیر نزولی.

 void quicksort (index low , index high)

 {

 index pivotpoint;

 if ( high > low) {

 partition (low , high , pivotpoint)

 quicksort (low , pivotpoint – 1)

  quicksort (pivotpoint + 1 , high);

 }

 }

الگوریتم7-2: افراز آرایه  

مسئله:  افراز آرایه S برای مرتب سازی سریع.

 void partition (index low, index high)

 index & pivotpoint)

 {

 index i , j;

  keytype pivotitem;

 pivotitem = S [low];

 j = low

 for ( i = low +1 ; i <= high; i ++)

 

 if ( S [i] < pivotitem ) {

 j++;

 exchange S [i] and S [j];

 }

 pivotpoint = j;

 exchange S [low] and S [ pivotpoint];

}

 

تحلیل پیچیدگی زمانی در حالت معمول برای الگوریتم 7-2( افراز)

 

عمل اصلی: مقایسهS [i]  با pivotitem .

اندازه ورودی: n = high – how +1 ، تعداد عناصرموجود در زیر آرایه.

 

T(n) = n - 1

 

تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم 6-2(مرتب سازی سریع)

 

عمل اصلی: مقایسهS [i]  با pivotitem در روال partition .

اندازه ورودی: n ، تعداد عناصر موجود درآرایه S.

 T(n) = T(0) + T( n – 1) + n – 1

   

زمان لازم برای افراز زمان لازم برای مرتب سازی   زمان لازم برای مرتب سازی  .    زیرآرایه طرف راست    زیر آرایه طرف چپ

 

 

 

 به ازای n > 0   T (n) = T (n – 1) + n – 1

 T (0) = 0

 

W (n) = n (n – 1) / 2 Є θ (n²)

 

تحلیل پیچیدگی زمانی در حالت میانگین برای الگوریتم 6-2(مرتب سازی سریع)

 

عمل اصلی: مقایسهS [i]  با pivotitem در partition .

اندازه ورودی: n ، تعداد عناصر موجود در S.

 

  A (n) Є θ (n lg n)

 

5-2الگوریتم ضرب ماتریس استراسن

 

پیچیدگی این الگوریتم از لحاظ ضرب، جمع و تفریق بهتر از پیچیدگی درجه سوم است.

روش استراسن در مورد ضرب ماتریس های 2×2 ارزش چندانی ندارد.

 

الگوریتم 8-2: استراسن

مسئله : تعیین حاصلضرب دو ماتریس n ×n که در آن n توانی از 2 است.

  void starssen ( int n

 n × n _ matrix A,

 n × n _ matrix B,

 n × n _ matrix & C)

 {

 if ( n <= threshold)

 compute C = A × B using the standard algorithm;

 

 else {

 partition A into four submatrics A11, A12 , A21,A22;

 partition B into four submatrics B11, B12 , B21,B22;

 compute C = A × B using Starssen’s Method;

 }

  }

 

 

تحلیل پیچیدگی زمانی تعداد ضرب ها در الگوریتم 8-2(استرسن)در حالت معمول

 

 عمل اصلی: یک ضرب ساده.

 اندازه ورودی:n  ، تعداد سطرها و ستون ها در ماتریس.

 

 به ازای n > 1  که n توانی از 2است  T (n) = 7 T (n / 2)

 T (1) = 1

 

  T (n) Є θ ( n ^2.81)

 

تحلیل پیچیدگی زمانی تعدادجمع هاو تفریقهای الگوریتم (استرسن)درحالت معمول

 

عمل اصلی: یک جمع یا تفریق ساده.

 اندازه ورودی:n  ، تعداد سطرها و ستون ها در ماتریس.

 

به ازای n > 1  که n توانی از 2است18 (n/2)²  +(T (n) = 7T(n/2

 T ( 1 ) = 1

 

 T ( n ) Є θ ( n ^ 2.81)

 

الگوریتم9-2: ضرب اعداد صحیح بزرگ

مسئله: ضرب دو عدد صحیح بزرگ u و v

 

 large _ integer prod ( large_integer u, large_integer v)

 {

 large_inreger x , y , w , z ;

 int n , m ;

 n = maximum(number of digits in u,number of digits in v)

 if (u = = 0 || v = = 0)

 return 0 ;

 

 else if (n < = threshold)

 return u × v obtained in the usual way;

 else {

 m = Į n / 2 ⌡;

 x = u divide 10 ^ m ; y = rem 10 ^ m;

 w = v divide 10 ^ m ; z = rem 10 ^ m;

  return prod (x ,w) × 10 ^2m + ( prod ( x, z) + prod (w, y )) × 10 ^ m + prod ( y, z);

 }

 }

تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم9-2( ضرب اعداد صحیح)

 

 عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در

 هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ،

 rem 10 ^m یا  ×10 ^ m. هر یک از این اعمال را m  بار انجام می دهد.

اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح.

 

 به ازای n > s  که n توانی از 2استW ( n ) = 4 W (n / 2) + cn 

W ( s ) = 0

 

W ( n ) Є θ ( n² )

 

الگوریتم 10-2: ضرب اعداد صحیح بزرگ 2

  large_integer prod2 (large_integer u , large_ integer v)

 {

 large_integer x , y , w , z , r , p , q;

 int n , m;

 n = maximum (number of digits in u,number of digits in v);

 if (u = = 0 || v = = 0)

 return 0 ;

 else if (n < = threshold)

 return u × v obtained in the usual way; 

 else {

 m = Į n / 2 ⌡;

  x = u divide 10 ^ m ; y = rem 10 ^ m;

 w = v divide 10 ^ m ; z = rem 10 ^ m;

 r = prod2 (x + y, w + z );

 p = prod2 ( x , w )

 q = prod2 ( y , z );

 return p ×10 ^ 2m + ( r – p – q ) × 10 ^ m +q ; }

 }

 

تحلیل پیچیدگی زمانی در بدترین حالت برای الگوریتم10-2( ضرب اعداد صحیح2)

عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در

 هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ،

 rem 10 ^m یا  ×10 ^ m. هر یک از این اعمال را m  بار انجام می دهد.

اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح.

 

به ازای n > s  که n توانی از 2است

3W(n/2)+ c n <=W (n) <= 3W (n / 2 +1) + c n

 W (s) = 0

W (n) = θ (n ^ 1.58)

 

 

 

+ نوشته شده در شنبه یازدهم خرداد 1387ساعت 13:12 توسط میلاد |