الگوریتم

الگوریتم

اسلاید 1: الگوریتم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 ;

اسلاید 2: 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); } }

اسلاید 3: تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم( ضرب اعداد صحیح) عمل اصلی: دستکاری یک رقم دهدهی در یک عدد صحیح بزرگ در هنگام جمع کردن ، تفریق کردن، یا انجام اعمالdivide 10 ^ m ، rem 10 ^m یا ×10 ^ m. هر یک از این اعمال را m بار انجام می دهد.اندازه ورودی: n ، تعداد ارقام هر یک از دو عدد صحیح. به ازای n > s که n توانی از 2استT ( n ) = 4 T (n / 2) + cn T ( s ) = 0 T ( n ) Є θ ( n² )

اسلاید 4: در چه مسائلی نمی توان از روش تقسیم وحل استفاده کرد1- مسایلی با اندازه n به چند زیر مسئله تقسیم می شود که اندازه زیر مسئله ها نیز تقریبا برابر n است. زمان نمایی ایجاد می کند.2- مساله ای با اندازه n تقریبا به اندازه n زیر مسئله با اندازه n/c که در آن c ثابت است تقسیم می شود. زمان nlogn ایجاد می کند.

اسلاید 5: فرش کردن صفحه شطرنجی ابعاد صفحه 2k*2k است.موزاییک به شکل L است.در بدترین حالت یکی از خانه ها خالی می ماند.

اسلاید 6: 4*4

اسلاید 7:

اسلاید 8:

اسلاید 9:

اسلاید 10:

اسلاید 11:

اسلاید 12:

اسلاید 13: ضرب چند جمله ای ها P(x)=anxn+an-1xn-1+an-2xn-2 . . . a2x2 + a1x1+a0Q(x)=bnxn+bn-1xn-1+bn-2xn-2 . . . b2x2 + b1x1+b0R(x)= P(x)Q(x)

اسلاید 14: P(x)=anxn+an-1xn-1+an-2xn-2 . . . a2x2 + a1x1+a0Q(x)=bnxn+bn-1xn-1+bn-2xn-2 . . . b2x2 + b1x1+b0R(x)= P(x)Q(x)=a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1 a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2 ...

اسلاید 15: R(x)= P(x)Q(x)=a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1 a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2 ...a0b0

اسلاید 16: R(x)= P(x)Q(x)=a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1 a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2 ...a0b0 + (a1b0+a0b1)x +

اسلاید 17: R(x)= P(x)Q(x)=a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1 a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2 ...a0b0 + (a1b0+a0b1)x + (a0b2 + a1b1 + a2b0)x2 +

اسلاید 18: R(x)= P(x)Q(x)=a0b0 + a0b1x1+a0b2x2 + . .+ a0bn-2xn-2 + a0bn-1xn-1 + a0bnxn a1b0x+ a1b1x2+a1b2x3 + . .+ a1bn-2xn-1 + a1bn-1xn + a1bnxn+1 a2b0 x2+ a2b1x3+a2b2x4 + . .+ a2bn-2xn + a2bn-1xn+1 + a2bnxn+2 ...a0b0 + (a1b0+a0b1)x + (a0b2 + a1b1 + a2b0)x2 + . . . k جمله ام=ci=ki=0R(x)= P(x)Q(x)= 2ni=0cixiaibk-i

اسلاید 19: R(x)= P(x)Q(x)= 2ni=0cixiنیاز به دو for برای محاسبه بنابراین : O(n2)

اسلاید 20: روش تقسیم وحل برای ضرب چند جمله ایها R(x)= P(x)Q(x)P(x) =Ax(n/2) + BQ(x) = C x(n/2) + DA , B ,C ,D جند جمله ای از مرتبه n/2 است.R(x)= P(x)Q(x)=(Ax(n/2)+B)(Cx(n/2) +D) = ACxn +(AD+BC)x(n/2)+BDتعداد ضرب ها 4 تا است. عمل ضرب T(n)=4T(n/2)+cn T(n)=θ(n2)الگوریتم بهتر نشده است.

اسلاید 21: R(x)= P(x)Q(x)=(Ax(n/2)+B)(Cx(n/2) +D) = ACxn +(AD+BC)x(n/2)+BDAD+BC=(A-B)(D-C)+AC+BDR(x)= ACxn +((A-B)(D-C)+AC+BD)x(n/2)+BDR(x)= ACxn +((A-B)(D-C)+AC+BD)x(n/2)+BDسه ضرب لازم است.T(n)=3T(n/2)+cnT(n)= θ(nlog 3)عملکرد بهتر است.