В.Б. Алексеев - Введение в теорию сложности алгоритмов (1158872), страница 4
Текст из файла (страница 4)
Óìíîæåíèå n+1-ðàçðÿäíûõ ÷èñåë (X1 +X2 )(Y1 +Y2 ) ìîæíî (êàê óêàçàíî âûøå) ñâåñòè ê óìíîæåíèþ n-ðàçðÿäíûõ ÷èñåë.Òàêèì îáðàçîì, óìíîæåíèå äâóõ 2n-ðàçðÿäíûõ ÷èñåë ñâîäèòñÿ ê òðåìóìíîæåíèÿì n-ðàçðÿäíûõ ÷èñåë è O(n) äîïîëíèòåëüíûõ îïåðàöèé. Âðåçóëüòàòå äëÿ ñëîæíîñòè LÊ (n) àëãîðèòìà Êàðàöóáû èìååìLÊ (2n) 6 3LÊ (n) + O(n).Äëÿ n = 1 ïðèìåíÿåì îáû÷íûé àëãîðèòì (îäíà êîíúþíêöèÿ), äëÿ n = 2k(k = 1, 2, 3, . . . ) ïðèìåíÿåì îïèñàííóþ ðåêóðñèþ, äëÿ 2k−1 < n 6 2käîïèñûâàåì â ïåðåìíîæàåìûå ÷èñëà ñïåðåäè íóëè, äåëàÿ äëèíó ðàâíîé2k , è ïðèìåíÿåì ðåêóðñèâíûé àëãîðèòì äëÿ 2k -ðàçðÿäíûõ ÷èñåë.
Âðåçóëüòàòå ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå äëÿ îïèñàííîãîàëãîðèòìà Êàðàöóáû ïîëó÷àåìLÊ (n) = O(nlog2 3 ).17Òåîðåìà äîêàçàíà.2.4. Àëãîðèòì Òîîìà äëÿ óìíîæåíèÿ ÷èñåëÇäåñü ìû ðàññìîòðèì åùå áîëåå áûñòðûé àëãîðèòì äëÿ óìíîæåíèÿ÷èñåë, êîòîðûé ïðåäëîæèë À. Ë. Òîîì [15]. Íàì ïîòðåáóåòñÿ ñëåäóþùèéèçâåñòíûé ôàêò î ìíîãî÷ëåíàõ.Óòâåðæäåíèå (èíòåðïîëÿöèîííàÿ ôîðìóëà Ëàãðàíæà). ÏóñòüP (x) = cn xn + cn−1 xn−1 + . .
. + c1 x + c0 ïðîèçâîëüíûé ïîëèíîì ñòåïåíè n, çíà÷åíèÿ êîòîðîãî P (dm ) èçâåñòíû â n + 1 ðàçëè÷íûõ òî÷êàõd1 , d2 , . . . , dn+1 . Òîãäà ñóùåñòâóþò òàêèå êîíñòàíòû αkm , çàâèñÿùèåòîëüêî îò d1 , d2 , . . . , dn+1 , ÷òîcq =n+1Xαqm P (dm ), q = 0, 1, . . . , n.(2.4)i=1Ïðè ýòîì, åñëè âñådmαkm ðàöèîíàëüíû.ôèêñèðîâàííîãî ε > 0 âûïîëíÿåòñÿðàöèîíàëüíû, òî è âñåÒåîðåìà 2.6. Äëÿ ëþáîãîM (n) = O(n1+ε ), ãäå M (n) ìèíèìàëüíàÿ áèòîâàÿ ñëîæíîñòü óìíîæåíèÿ äâóõ n-ðàçðÿäíûõ äâîè÷íûõ ÷èñåë.Äîêàçàòåëüñòâî.
Çàôèêñèðóåì íàòóðàëüíîå k > 2 è ðàññìîòðèìñëåäóþùèé àëãîðèòì Òîîìà [15] äëÿ óìíîæåíèÿ n-ðàçðÿäíûõ äâîè÷íûõ÷èñåë A è B . Åñëè k m−1 < n 6 k m , òî óâåëè÷èì ðàçðÿäíîñòü äî k m ,ïðèïèñûâàÿ ñïåðåäè íóëè. Äëÿ n = k m ïîñòóïàåì ñëåäóþùèì îáðàçîì.Ðåæåì A è B íà k êóñêîâ äëèíû k m−1 . Ïóñòü A = (Ak−1 Ak−2 . . . A1 A0 )2è B = (Bk−1 Bk−2 . . . B1 B0 )2 . Ðàññìîòðèì ìíîãî÷ëåíû f (x) = Ak−1 xk−1 +Ak−2 xk−2 + . . . + A1 x + A0 è g(x) = Bk−1 xk−1 + Bk−2 xk−2 + . . . + B1 x + B0 .m−1m−1m−1Òîãäà A = f (2k ), B = g(2k ) è èñêîìîå C = A · B = f (2k ) ·m−1m−1g(2k ) = h(2k ), ãäå h(x) = f (x)·g(x). Çàìåòèì, ÷òî h(x) ìíîãî÷ëåíñòåïåíè 2k − 2. Àëãîðèòì ñîñòîèò èç ñëåäóþùèõ øàãîâ.1.
Âû÷èñëÿåì f (dm ) è g(dm ), ãäå d1 , d2 , . . . , d2k−1 ëþáûå ôèêñèðîâàííûå öåëûå òî÷êè (íàïðèìåð, dm = 0, ±1, ±2, . . . , ±(k − 1)).2. Âû÷èñëÿåì h(dm ) = f (dm )g(dm ) òåì æå àëãîðèòìîì äëÿ n =m−1k(ìû óòî÷íèì ýòî íèæå).3. Ïî ôîðìóëå (2.4) âû÷èñëÿåì êîýôôèöèåíòû cq (q = 0, 1, . . .
, 2k −2) ìíîãî÷ëåíà h(x).m−14. Âû÷èñëÿåì h(2k ) = C = AB .Îöåíèì òåïåðü ñëîæíîñòü êàæäîãî øàãà. Îòìåòèì, ÷òî k m = n,k m−1 = nk è k êîíñòàíòà.Øàã 1. Íà ýòîì øàãå âû÷èñëÿåì f (dm ) è g(dm ) íåïîñðåäñòâåííîïî ôîðìóëàì ìíîãî÷ëåíîâ, âûïîëíÿÿ âñå îïåðàöèè "â ñòîëáèê". Ïðè18ýòîì, òàê êàê âñå dm êîíñòàíòû è k êîíñòàíòà, âû÷èñëåíèå âñåõdlm (m = 1, 2, . . . , 2k − 1; l = 2, 3, . . . , k − 1) òðåáóåò êîíñòàíòíîãî÷èñëà áèòîâûõ îïåðàöèé è äëèíû âñåõ ïîëó÷àåìûõ ÷èñåë îãðàíè÷åíûêîíñòàíòîé (çàâèñÿùåé îò k , íî íå çàâèñÿùåé îò n).
Ïîýòîìó âû÷èñëåíèå âñåõ îäíî÷ëåíîâ Al dlm òðåáóåò O(n) áèòîâûõ îïåðàöèé è äëèíûïîëó÷àåìûõ ÷èñåë íå ïðåâîñõîäÿò nk + const. Àíàëîãè÷íî äëÿ Bl dlm .Ñêëàäûâàÿ ýòè îäíî÷ëåíû (k êîíñòàíòà), ïîëó÷àåì, ÷òî âû÷èñëåíèåâñåõ çíà÷åíèé f (dm ) è g(dm ) òðåáóåò O(n) áèòîâûõ îïåðàöèé è äëèíàâñåõ ýòèõ çíà÷åíèé íå ïðåâîñõîäèò nk + const.Øàã 2. Íà ýòîì øàãå íàì íàäî 2k−1 ðàç ïåðåìíîæèòü ÷èñëà äëèíûíå áîëåå nk + const. Ïóñòü C è D 2 òàêèõ ÷èñëà, è C = (C1 C0 )2 , D =n(D1 D0 )2 , ãäå äëèíà ÷èñåë C0 è D0 ðàâíà nk . Òîãäà C·D = (C1 ·2 k +C0 )·(D1 ·n2nn2 k +D0 ) = C1 D1 ·2 k +(C1 D0 +C0 D1 )·2 k +C0 D0 . Áóäåì âû÷èñëÿòü C1 D1 ,C1 D0 , C0 D1 â ñòîëáèê, à C0 D0 ðåêóðñèâíî òåì æå àëãîðèòìîì, åñëèäëèíà C0 è D0 , ðàâíàÿ k m−1 , áîëüøå 1.
Åñëè æå k m−1 = 1, òî C0 D0 òàêæåâû÷èñëÿåì â ñòîëáèê. Ïóñòü LT (n) áèòîâàÿ ñëîæíîñòü àëãîðèòìàÒîîìà (â õóäøåì ñëó÷àå) äëÿ óìíîæåíèÿ ÷èñåë äëèíû n. Òîãäà ÷èñëîîïåðàöèé íà øàãå 2 íå ïðåâîñõîäèò (2k−1)LT ( nk )+O(n), è ïîëó÷àþùèåñÿ÷èñëà èìåþò äëèíó O(n).Øàã 3. Òàê êàê âñå dm öåëûå, òî âñå αqm â ôîðìóëå (2.4)βðàöèîíàëüíûå. Ïóñòü β èõ îáùèé çíàìåíàòåëü è αqm = βqm . ÒîãäàP2k−1âñå βqm öåëûå è cq = β1 m=1 βqm h(dm ). Òàê êàê k êîíñòàíòà, âñåβqm êîíñòàíòûP2k−1 è äëèíà âñåõ ÷èñåë h(dm ) åñòü O(n), òî äëÿ âû÷èñëåíèÿâñåõ ñóìì m=1 βqm h(dm ), q = 0, 1, . .
. , 2k − 1, òðåáóåòñÿ O(n) áèòîâûõîïåðàöèé è ïðè ýòîì ïîëó÷àþòñÿ ÷èñëà äëèíû O(n). Òàê êàê β êîíñòàíòà, òî âû÷èñëåíèå âñåõ cq (êîòîðûå çàâåäîìî äîëæíû áûòü öåëûìè,êàê êîýôôèöèåíòû ìíîãî÷ëåíà h(x) = f (x)g(x)) òðåáóåò O(n) áèòîâûõîïåðàöèé (äåëèì â ñòîëáèê), è âñå cq èìåþò äëèíó O(n).m−1Øàã 4. Âû÷èñëåíèå h(2k ) ñâîäèòñÿ ê ñëîæåíèþ ÷èñåë cq , ñäâèíóòûõ âëåâî íå áîëåå, ÷åì íà n ðàçðÿäîâ. Òàê êàê ÷èñåë cq êîíñòàíòíîåm−1êîëè÷åñòâî, òî âû÷èñëåíèå h(2k ) = C = AB òðåáóåò O(n) áèòîâûõîïåðàöèé.Äëÿ îáùåãî ÷èñëà LT (n) áèòîâûõ îïåðàöèé â îïèñàííîì àëãîðèòìå(ïðè n = k m ) èìååìnLT (n) 6 (2k − 1)LT ( ) + O(n).kÒîãäà ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå äëÿ âñåõ n ïîëó÷àåìLT (n) = O(nlogk (2k−1) ).19C ðîñòîì k èìååì1logk (2k − 1) = 1 + logk (2 − ) −→ 1.kÏîýòîìó äëÿ ëþáîãî ε > 0 ìîæíî âûáðàòü k òàê, ÷òî logk (2k − 1) < 1 + εè LT (n) = O(n1+ε ). Òåîðåìà äîêàçàíà.Çàìå÷àíèå.
Åùå áîëåå áûñòðûì ÿâëÿåòñÿ àëãîðèòì óìíîæåíèÿ÷èñåë Øåíõàãå è Øòðàññåíà, áèòîâàÿ ñëîæíîñòü êîòîðîãî ðàâíàO(n log n log log n) [16].2.5. Àëãîðèòì Øòðàññåíà äëÿ óìíîæåíèÿ ìàòðèöÐàññìîòðèì çàäà÷ó óìíîæåíèÿ äâóõ êâàäðàòíûõ ìàòðèö A = kaij kè B = kbkl k ïîðÿäêà n. Ïóñòü A · B = C = kcrs k.
Òîãäà ïî îïðåäåëåPníèþ crs =p=1 arp bps .  êà÷åñòâå âõîäà ìû áóäåì ðàññìàòðèâàòü âñåçíà÷åíèÿ aij è bkl , ñ÷èòàÿ èõ íåäåëèìûìè, òî åñòü ìû âîñïðèíèìàåìèõ êàê åäèíîå öåëîå è íå ìîæåì ðàáîòàòü ñ êàêèìè-ëèáî èõ ÷àñòÿìè. êà÷åñòâå îïåðàöèé áóäåì ðàññìàòðèâàòü 4 àðèôìåòè÷åñêèå îïåðàöèè,êîòîðûå ìîãóò ïðèìåíÿòüñÿ êàê ê èñõîäíûì ïåðåìåííûì aij , bkl , òàêè ê óæå ïîñòðîåííûì âûðàæåíèÿì. Íàøà çàäà÷à ñîñòîèò â ïîëó÷åíèèâñåõ âûðàæåíèé äëÿ crs .
Ñëîæíîñòüþ àëãîðèòìà áóäåò ñ÷èòàòüñÿ ÷èñëîàðèôìåòè÷åñêèõ îïåðàöèé.Îáû÷íûé àëãîðèòì óìíîæåíèÿ ìàòðèö (ñòðî÷êà íà ñòîëáåö) òðåáóåò n3 óìíîæåíèé è n2 (n − 1) ñëîæåíèé, òî åñòü ïîðÿäêà n3 îïåðàöèé.Áîëåå áûñòðûé ïî ïîðÿäêó àëãîðèòì òèïà ðàçäåëÿé è âëàñòâóé ïðåäëîæèë Øòðàññåí [17].Òåîðåìà 2.7 (Â. Øòðàññåí). Äëÿ óìíîæåíèÿ äâóõ ìàòðèö ïîðÿäêà n ñóùåñòâóåò àëãîðèòì ñ ÷èñëîì àðèôìåòè÷åñêèõ îïåðàöèélog2 7O(n).Îïèøåì òàêîé àëãîðèòì.
Åñëè n íå ñòåïåíüäâîéêè è áëèæàéøàÿ ê n ñâåðõó ñòåïåíü äâîéêè åñòü 2k , òî ðàñøèðèìäàííûå ìàòðèöû A è B äî ìàòðèö A0 è B 0 ïîðÿäêà 2k òàê, ÷òîáû â ëåâûõâåðõíèõ óãëàõ ìàòðèö A0 è B 0 ñòîÿëè, ñîîòâåòñòâåííî, A è B , à îñòàëüíûåýëåìåíòû áûëè ðàâíû 0. Òîãäà, åñëè A0 · B 0 = C 0 , òî ëåãêî âèäåòü, ÷òî âC 0 â ëåâîì âåðõíåì óãëó ñòîèò ìàòðèöà C = A · B , à îñòàëüíûå ýëåìåíòûðàâíû 0. Ïîýòîìó äëÿ âû÷èñëåíèÿ C = A · B äîñòàòî÷íî ïåðåìíîæèòüìàòðèöû A0 è B 0 ïîðÿäêà 2k . Ïóñòü äàëåå n = 2k ñòåïåíü äâîéêè èA, B ìàòðèöû ïîðÿäêà n = 2k .
Ðàçðåæåì êàæäóþ èç ìàòðèö A è B ,à òàêæå èñêîìóþ ìàòðèöó C = A · B , íà 4 êâàäðàòíûõ áëîêà ðàçìåðàÄîêàçàòåëüñòâî.20n2× n2 : A11 A12A= A21 A22 , B = B11 B12 B21 B22 , C = C11 C12 C21 C22.Èç àëãåáðû èçâåñòíî, ÷òî â ýòîì ñëó÷àåC11 = A11 B11 + A12 B21 ,C12 = A11 B12 + A12 B22 ,C21 = A21 B11 + A22 B21 ,C22 = A21 B12 + A22 B22 .Òàêèì îáðàçîì, âû÷èñëåíèå ìàòðèöû C ñâîäèòñÿ ê 8 óìíîæåíèÿì ìàòðèö ïîðÿäêà n2 (è íåñêîëüêèì ñëîæåíèÿì). Èäåÿ Øòðàññåíà ñîñòîèò âçàìåíå 8 óìíîæåíèé íà 7 (ñðàâíèòå ñ àëãîðèòìîì Êàðàöóáû). Ðàññìîòðèì ñëåäóþùèå 7 ïðîèçâåäåíèé:D1D2D3D4= (A11 + A22 )(B11 + B22 ),D5 = (A11 + A12 )B22 ,= (−A11 + A21 )(B11 + B12 ), D6 = A22 (−B11 + B21 ),= (A12 − A22 )(B21 + B22 ),D7 = (A21 + A22 )B11 .= A11 (B12 − B22 ),Ðàñêðûâàÿ ñêîáêè è ïðèâîäÿ ïîäîáíûå ÷ëåíû, ìîæíî ïðîâåðèòü, ÷òîC11 = D1 + D3 − D5 + D6 , C12 = D4 + D5 ,C21 = D6 + D7 ,C22 = D1 + D2 + D4 − D7 .Òàêèì îáðàçîì, óìíîæåíèå ìàòðèö ïîðÿäêà n ñâîäèòñÿ ê 7 óìíîæåíèÿììàòðèö ïîðÿäêà n2 è íåñêîëüêèì ñëîæåíèÿì ìàòðèö ïîðÿäêà n2 .
Åñëè n =2k , òî ýòîò ïðîöåññ ìîæíî ïðîäîëæèòü ðåêóðñèâíî. Åñëè æå n = 1, òî äëÿóìíîæåíèÿ ìàòðèö ïîðÿäêà 1 òðåáóåòñÿ âñåãî 1 óìíîæåíèå ýëåìåíòîâ.Ïóñòü L(n) ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé â îïèñàííîì àëãîðèòìå.Òàê êàê ñëîæåíèå äâóõ ìàòðèö ïîðÿäêà n2 òðåáóåò O(n2 ) îïåðàöèé, òîäëÿ n = 2k (k = 1, 2, 3, .
. .) ïîëó÷àåì ðåêóððåíòíîå íåðàâåíñòâînL(n) 6 7L( ) + O(n2 ).2Ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå îòñþäà ïîëó÷àåì L(n) =O(nlog2 7 ). Òåîðåìà äîêàçàíà.Çàìå÷àíèå. Îæèäàåòñÿ, ÷òî äëÿ óìíîæåíèÿ ìàòðèö ïîðÿäêà nñóùåñòâóåò àëãîðèòì ñ ÷èñëîì àðèôìåòè÷åñêèõ îïåðàöèé O(n2+ε ) äëÿëþáîãî ôèêñèðîâàííîãî ε > 0 (ñðàâíèòå ñ àëãîðèòìîì Òîîìà), îäíàêîïîêà (ñåðåäèíà 2002 ãîäà) íàèëó÷øåé îöåíêîé ÿâëÿåòñÿ O(n2.38 ) [2].213. Ìåòîä ðàñøèðåíèÿ ìîäåëèÎ÷åíü âàæíûì ìåòîäîì â ìàòåìàòèêå ÿâëÿåòñÿ ìåòîä ðàñøèðåíèÿìîäåëè. Ïåðåõîä â áîëåå øèðîêóþ ìîäåëü îáû÷íî íå óïðîùàåò çàäà÷ó,íî ðàñøèðÿÿ âîçìîæíîñòè, óïðîùàåò ïîèñê ðåøåíèÿ çàäà÷è.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
