В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 4
Текст из файла (страница 4)
Àëãîðèòì Êàðàöóáû äëÿ óìíîæåíèÿ ÷èñåëÅñëè òðåáóåòñÿ ñëîæèòü äâà n-ðàçðÿäíûõ ÷èñëà, òî ìîæíî ïðîèçâåñòè ñëîæåíèå â ñòîëáèê. Ïðè ýòîì â êàæäîì ðàçðÿäå íàì íóæíî âçàâèñèìîñòè îò çíà÷åíèé äàííîãî ðàçðÿäà â ñëàãàåìûõ è îò âåëè÷èíûïåðåíîñà èç ïðåäûäóùåãî ðàçðÿäà âû÷èñëèòü ðàçðÿä ñóììû è âåëè÷èíóïåðåíîñà â ñëåäóþùèé ðàçðÿä. Äëÿ îäíîãî ðàçðÿäà ýòî òðåáóåò êîíñòàíòíîãî ÷èñëà îïåðàöèé, à â öåëîì äëÿ ñëîæåíèÿ äâóõ n-ðàçðÿäíûõ÷èñåë O(n) îïåðàöèé íàä ðàçðÿäàìè.
Àíàëîãè÷íóþ îöåíêó O(n) ìîæíîïîëó÷èòü è äëÿ ñëîæíîñòè âû÷èòàíèÿ â ñòîëáèê. Òîëüêî çäåñü âìåñòîïåðåíîñà â ñëåäóþùèé ðàçðÿä ôîðìèðóåòñÿ çàïðîñ èç ñëåäóþùåãî ðàçðÿäà.Åñëè äâà n-ðàçðÿäíûõ ÷èñëà óìíîæàòü â ñòîëáèê, òî âñå ðàçðÿäûïåðâîãî ÷èñëà ñíà÷àëà íàäî óìíîæàòü íà ïåðâûé ðàçðÿä âòîðîãî ÷èñëà,çàòåì íà ñëåäóþùèé ðàçðÿä è ò.
ä. Òàêèì îáðàçîì ÷èñëî îïåðàöèé íàäðàçðÿäàìè áóäåò íå ìåíåå n2 . Áîëåå áûñòðûé (ïî ïîðÿäêó) àëãîðèòìïðåäëîæèë À. À. Êàðàöóáà [8], è èìåííî ýòîò àëãîðèòì ñ÷èòàåòñÿ ïåðâûìàëãîðèòìîì òèïà ðàçäåëÿé è âëàñòâóé.Äëÿ ïðîñòîòû ìû íå áóäåì ðàññìàòðèâàòü àäðåñàöèþ, à áóäåì âêà÷åñòâå àëãîðèòìîâ ðàññìàòðèâàòü ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ â áàçèñå èç âñåõ äâóõìåñòíûõ áóëåâñêèõ îïåðàöèé è ïîä ñëîæíîñòüþàëãîðèòìà ïîíèìàòü ÷èñëî ýëåìåíòîâ â ñõåìå.  ýòîì ñëó÷àå ãîâîðÿò îáèòîâîé ñëîæíîñòè àëãîðèòìà.Òåîðåìà 2.5 (Êàðàöóáà À. À.).
Äëÿ óìíîæåíèÿ äâóõ äâîè÷-n-ðàçðÿäíûõ ÷èñåë ñóùåñòâóåò àëãîðèòì ñ áèòîâîé ñëîæíîñòüþlog2 3O(n).íûõÏîêàæåì ñíà÷àëà, ÷òî àëãîðèòì (ñõåìó) äëÿóìíîæåíèÿ (n + 1)-ðàçðÿäíûõ äâîè÷íûõ ÷èñåë ìîæíî ïîëó÷èòü, èñïîëüçóÿ àëãîðèòì (ñõåìó) äëÿ óìíîæåíèÿ n-ðàçðÿäíûõ äâîè÷íûõ ÷èñåë è äîïîëíèòåëüíî O(n) áèòîâûõ îïåðàöèé. Äåéñòâèòåëüíî, ïóñòüÄîêàçàòåëüñòâî.16òðåáóåòñÿ ïåðåìíîæèòü äâà (n + 1)-ðàçðÿäíûõ äâîè÷íûõ ÷èñëà X1 =(x0 , x1 , . . . , xn )2 è Y1 = (y0 , y1 , . . .
, yn )2 . Îáîçíà÷èì (x1 , x2 , . . . , xn )2 = Xè (y1 , y2 , . . . , yn )2 = Y . Ïðè ýòîì X1 = x0 2n + X , Y1 = y0 2n + Y èX1 Y1 = x0 y0 22n + (x0 Y + y0 X)2n + XY.Ïîýòîìó äëÿ âû÷èñëåíèÿ X1 Y1 äîñòàòî÷íî èñïîëüçîâàòü óìíîæèòåëüMn äëÿ âû÷èñëåíèÿ XY , 2n ýëåìåíòîâ äëÿ âû÷èñëåíèÿ x0 Y è y0 X ,1 ýëåìåíò äëÿ âû÷èñëåíèÿ x0 y0 è 3 ñóììàòîðà ïîðÿäêà (òî åñòü äëÿ÷èñëà ðàçðÿäîâ) íå áîëåå 2n + 2, òàê êàê X1 Y1 < 22n+2 .
Îòìåòèì,÷òî ÷èñëà x0 y0 è x0 Y + y0 X íàäî ïîäàâàòü íà ñóììàòîðû ñî ñäâèãîì,îäíîâðåìåííî ïîäàâàÿ íà ìëàäøèå ðàçðÿäû 0. Ïðè ýòîì 0 ìîæíî ïðåäâàðèòåëüíî ïîëó÷èòü ïîäñõåìîé ñ 2 ýëåìåíòàìè, ðåàëèçóþùåé x0 x̄0 = 0.Òàê êàê ñëîæíîñòü êàæäîãî ñóììàòîðà ìîæíî ñäåëàòü íå áîëåå O(n), òîñëîæíîñòü ïîëó÷åííîé ñõåìû áóäåò íå áîëüøå ÷åì L(Mn ) + O(n). Ïóñòüòåïåðü íóæíî ïåðåìíîæèòü äâà 2n-ðàçðÿäíûõ ÷èñëà X è Y . Ðàçîáüåìèõ íà ÷àñòè, ñîäåðæàùèå ïî n ðàçðÿäîâ.
Òîãäà ïîëó÷èì X = X1 2n + X2 ,Y = Y1 2n + Y2 . ÎòñþäàXY = X1 Y1 22n + (X1 Y2 + X2 Y1 )2n + X2 Y2 == X1 Y1 22n + [(X1 + X2 )(Y1 + Y2 ) − X1 Y1 − X2 Y2 ]2n + X2 Y2 .Òàê êàê X1 Y2 + X2 Y1 > 0, òî ïðè âû÷èòàíèè â êâàäðàòíîé ñêîáêå íåâîçíèêàåò îòðèöàòåëüíûõ ÷èñåë. Òàêèì îáðàçîì, óìíîæåíèå XY äâóõ2n-ðàçðÿäíûõ ÷èñåë ñâîäèòñÿ ê äâóì óìíîæåíèÿì n-ðàçðÿäíûõ ÷èñåëX1 Y1 è X2 Y2 , óìíîæåíèþ n + 1-ðàçðÿäíûõ ÷èñåë (X1 + X2 )(Y1 + Y2 ) èíåñêîëüêèì ñëîæåíèÿì è âû÷èòàíèÿì ÷èñåë ñ ÷èñëîì ðàçðÿäîâ íå áîëåå4n (òàê êàê XY < 24n ). Óìíîæåíèå 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+ε ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
