В.Б. Алекссев - Сложные алгоритмы (1132790), страница 4
Текст из файла (страница 4)
tAKOJ ALGORITM (SHEMA)IMEET SLOVNOSTX PO PORQDKU n2. sLEDU@]AQ TEOREMA POKAZYWAET, ^TOALGORITM UMNOVENIQ \W STOLBIK" NE OPTIMALEN PO PORQDKU.tEOREMA 6.4 (kARACUBAa. a. [4]). sU]ESTWUET TAKAQ KONlog3STANTA c ^TO LM (n) 6 cn 2 DLQ WSEH n,,..-1-.-,.16dOKAVEM SNA^ALA NESKOLXKO WSPOMOGATELXNYH LEMM.lEMMA 6.1.
sU]ESTWUET KONSTANTA c1 TAKAQ ^TO LM (n +1) 6LM (n) + c1n DLQ WSEH ndOKAZATELXSTWO. pUSTX TREBUETSQ PEREMNOVITX DWA (n +1)-RAZRQDNYH ^ISLA X1 = j(x0; x1 ; : : : ; xn )j I Y1 = j(y0; y1; : : : ; yn)j. tOGDAOBOZNA^IM j(x1; x2; : : : ; xn)j = X I j(y1; y2; : : : ; yn)j = Y . pRI \TOMX1 = x02n + X , Y1 = y02n + Y I,.X1Y1 = x0y022n + (x0Y + y0X )2n + XY:pO\TOMU DLQ WY^ISLENIQ X1Y1 DOSTATO^NO ISPOLXZOWATX UMNOVITELXMn DLQ WY^ISLENIQ XY , 2n \LEMENTOW DLQ WY^ISLENIQ x0Y I y0X , 1\LEMENT DLQ WY^ISLENIQ x0y0 I 3 SUMMATORA PORQDKA NE BOLEE 2n+2, TAKKAK X1Y1 < 22n+2.
oTMETIM, ^TO ^ISLA x0y0 I x0Y + y0X NADO PODAWATXNA SUMMATORY SO SDWIGOM, ODNOWREMENNO PODAWAQ NA MLAD[IE RAZRQDY0. pRI \TOM 0 MOVNO PREDWARITELXNO POLU^ITX PODSHEMOJ S 2 \LEMENTAMI, REALIZU@]EJ x0x0 = 0.tAK KAK SLOVNOSTX KAVDOGO SUMMATORAMOVNO SDELATX NE BOLEE 9(2n + 2), A SLOVNOSTX Mn RAWNOJ LM (n), TOSLOVNOSTX POLU^ENNOJ SHEMY BUDET NE BOLX[E ^EM LM (n) + c1n DLQNEKOTOROJ KONSTANTY c1. lEMMA DOKAZANA.lEMMA 6.2 (OSNOWNAQ).
sU]ESTWUET KONSTANTA c2 TAKAQ ^TOLM (2n) 6 3LM (n) + c2n DLQ WSEH ndOKAZATELXSTWO. pUSTX NUVNO PEREMNOVITX DWA 2n-RAZRQDNYH^ISLA X I Y . rAZOBXEM IH NA ^ASTI, SODERVA]IE PO n RAZRQDOW. tOGDAPOLU^IM X = X12n + X2, Y = Y12n + Y2. oTS@DAXY = X1Y122n + (X1Y2 + X2Y1)2n + X2Y2 == X1Y122n + [(X1 + X2)(Y1 + Y2) ; X1Y1 ; X2Y2]2n + X2Y2:tAK KAK X1Y2 + X2Y1 > 0, TO PRI WY^ITANII W KWADRATNOJ SKOBKE NEWOZNIKAET OTRICATELXNYH ^ISEL. tAKIM OBRAZOM, SHEMU DLQ UMNOVENIQ XY MOVNO POSTROITX, ISPOLXZUQ 2 OPTIMALXNYH UMNOVITELQ MnS ^ISLOM \LEMENTOW LM (n) W KAVDOM DLQ WY^ISLENIQ X1Y1 I X2Y2,UMNOVITELX Mn+1 S ^ISLOM \LEMENTOW LM (n + 1) DLQ WY^ISLENIQ(X1 + X2)(Y1 + Y2), 4 SUMMATORA PORQDKA NE BOLEE 4n (TAK KAK XY < 24n)I 2 WY^ITATELQ PORQDKA 2n + 2. w NEKOTORYH SUMMATORAH OPQTX NAMLAD[IE RAZRQDY NADO PODAWATX 0, KOTORYJ REALIZUEM PODSHEMOJ S 2\LEMENTAMI: 0 = xx, GDE x - L@BAQ WHODNAQ PEREMENNAQ.
dLQ POSTROENNOJ SHEMY M2n S U^ETOM LEMMY 6.1 POLU^IM DLQ NEKOTORYH KONSTANT cI c2:L(M2n) 6 2LM (n) + LM (n + 1) + cn 6 3LM (n) + c1n + cn = 3LM (n) + c2n,.17.lEMMA 6.3. sU]ESTWUET TAKAQKONSTANTA c3 ^TO DLQ L@BOGOkk,NATURALXNOGO k WYPOLNQETSQ LM (2 ) 6 c33kdOKAZATELXSTWO. pOLOVIM f (k) = LM3(2k ) . tOGDA IZ PREDYDU]EJLEMMY IMEEMLM (2k ) 6 LM (2k;1) + c2 ( 2 )k;1.I3k3k;13 3f (k) 6 f (k ; 1) + c32 ( 23 )k;1 6 f (k ; 2) + c32 ( 23 )k;2 + c32 ( 32 )k;1 66 : : : 6 f (1) + c32 [ 32 + ( 23 )2 + + ( 32 )k;1] 6 c3DLQ NEKOTOROJ KONSTANTY c3, POSKOLXKU SUMMA W KWADRATNYH SKOBKAH NEPREWOSHODIT SUMMU 2 BESKONE^NO UBYWA@]EJ GEOMETRI^ESKOJ PROGRESk)L(222MSII S PERWYM ^LENOM 3 I ZNAMENATELEM 3 . tAKIM OBRAZOM 3k 6 c3 ILM (2k ) 6 c33k .dOKAZATELXSTWO TEOREMY kARACUBY.
pUSTX n | L@BOE NATURALXNOE ^ISLO I n > 1. tOGDA SU]ESTWUET NATURALXNOE k TAKOE, ^TO2k;1 < n 6 2k . dLQ UMNOVENIQ n-RAZRQDNYH ^ISEL BUDEM ISPOLXZOWATXSHEMU M2k S ^ISLOM \LEMENTOW LM (2k ), PODAWAQ NA STAR[IE 2k ; n WHODNYH RAZRQDOW OBOIH SOMNOVITELEJ 0, PREDWARITELXNO REALIZOWANNYJPODSHEMOJ IZ 2 \LEMENTOW. tOGDA IMEEMLM (n) 6 LM (2k ) + 2 6 c33k + 2 = 3c33k;1 + 2 == 3c32(k;1) log2 3 + 2 < 3c3nlog2 3 + 2 6 cnlog2 3DLQ NEKOTOROJ KONSTANTY c.w ZAKL@^ENIE OTMETIM, ^TO SU]ESTWUET ALGORITM {ENHAGE I{TRASSENA DLQ UMNOVENIQ DWUH n-RAZRQDNYH ^ISEL, DA@]IJ OCENKULM (n) 6 cn log n log log n, GDE c | NEKOTORAQ KONSTANTA I LOGARIFMYMOVNO S^ITATX DWOI^NYMI.18aLGORITM tOOMAnAM POTREBUETSQ SLEDU@]IJ IZWESTNYJ FAKT O MNOGO^LENAH.uTWERVDENIE(INTERPOLQCIONNAQ FORMULA lAGRANVA).
pUSTXnn;1P (x) = cnx + cn;1x + : : : + c1x + c0 PROIZWOLXNYJ POLINOM STEPENIn ZNA^ENIQ KOTOROGO P (dm ) IZWESTNY W n + 1 RAZLI^NYH TO^KAHd1; d2; : : : ; dn+1 tOGDA SU]ESTWU@T TAKIE KONSTANTY km ZAWISQ]IETOLXKO OT d1; d2 ; : : : ; dn+1 ^TO|,.,,cq =n+1Xi=1qmP (dm ); q = 0; 1; : : : ; n:pRI \TOM ESLI WSE dm RACIONALXNY TO I WSE km RACIONALXNYtEOREMA. dLQ L@BOGO FIKSIROWANNOGO " > 0 WYPOLNQETSQ1+"M (n) = O(n ):dOKAZATELXSTWO zAFIKSIRUEM NATURALXNOE k > 2 I RASSMOTRIMSLEDU@]IJ ALGORITM tOOMA DLQ UMNOVENIQ n-RAZRQDNYH DWOI^NYH^ISEL A I B . eSLI km;1 < n 6 km , TO UWELI^IM RAZRQDNOSTX DO km ,PRIPISYWAQ SPEREDI NULI.
dLQ n = km POSTUPAEM SLEDU@]IM OBRAZOM.rEVEM A I B NA k KUSKOW DLINY km;1 . pUSTX A = (Ak;1Ak;2 : : : A1A0)2I B = (Bk;1Bk;2 : : : B1B0 )2. rASSMOTRIM MNOGO^LENY f (x) = Ak;1xk;1 +Ak;2xk;2+: :m:;+1 A1x+A0 I gm(;x1 ) = Bk;1xk;1 +Bk;2xk;2 +: : :+m;B1 1x+B0m.;tOG1kkkkDA Am;=1 f (2 ), B = g(2 ) I ISKOMOE C = A B = f (2 ) g(2 ) =h(2k ), GDE h(x) = f (x) g(x). zAMETIM, ^TO h(x) | MNOGO^LEN STEPENI2k ; 2. aLGORITM SOSTOIT IZ SLEDU@]IH [AGOW.1.wY^ISLQEM f (xm ) I g(xm ), GDE x1; x2; ; : : : ; x2k;1 |L@BYE FIKSIROWANNYE CELYE TO^KI (NAPRIMER, xm = 0; 1; 2; : : : ; (k ; 1)).2.wY^ISLQEM h(xm) = f (xm )g(xm) TEM VE ALGORITMOM DLQ n =km;1 (MY UTO^NIM \TO NIVE).3.
pO FORMULE ( ) WY^ISLQEM KO\FFICIENTY cq (q = 0; 1; : : : ; 2k ;1)MNOGO^LENA h(x).4. wY^ISLQEM h(2km;1 ) = C = AB .oCENIM TEPERX SLOVNOSTX KAVDOGO [AGA. oTMETIM, ^TO km = n,km;1 = nk I k | KONSTANTA.{AG 1. nA \TOM [AGE WY^ISLQEM f (xm ) I g(xm ) NEPOSREDSTWENNOPO FORMULAM MNOGO^LENOW, WYPOLNQQ WSE OPERACII "W STOLBIK". pRI\TOM, TAK KAK WSE xm | KONSTANTY I k | KONSTANTA, WY^ISLENIEWSEH xlm (m = 1; 2; : : : ; 2k ; 1; l = 2; 3; : : : ; k ; 1) TREBUET KONSTANTNOGO^ISLA BITOWYH OPERACIJ I DLINY WSEH POLU^AEMYH ^ISEL OGRANI^ENYKONSTANTOJ (ZAWISQ]EJ OT k, NO NE ZAWISQ]EJ OT n). pO\TOMU WY^ISLENIE WSEH ODNO^LENOW Al xlm TREBUET O(n) BITOWYH OPERACIJ I DLINY,,.19.POLU^AEMYH ^ISEL NE PREWOSHODQT nk + const. aNALOGI^NO DLQ Bl xlm .sKLADYWAQ \TI ODNO^LENY (k |KONSTANTA), POLU^AEM, ^TO WY^ISLENIEWSEH ZNA^ENIJ f (xm) I g(xm ) TREBUET O(n) BITOWYH OPERACIJ I DLINAWSEH \TIH ZNA^ENIJ NE PREWOSHODIT nk + const.{AG 2.
nA \TOM [AGE NAM NADO 2k ; 1 RAZ PEREMNOVITX ^ISLADLINY NE BOLEE nk + const. pUSTX C I D | 2 TAKIH ^ISLA, I C = (C1C0)2,D = (D1D0)2, GDE DLINA ^ISEL C0 I D0 RAWNA nk . tOGDA C D = (C1 2 nk + C0) (D1 2 nk + D0) = C1D1 2 2kn + (C1D0 + C0D1) 2 nk + C0D0:bUDEM WY^ISLQTX C1D1, C1D0, C0D1 "W STOLBIK", A C0D0 REKURSIWNOTEM VE ALGORITMOM, ESLI DLINA C0 I D0, RAWNAQ km;1 , BOLX[E 1. eSLIVE km;1 = 1, TO C0D0 TAKVE WY^ISLQEM "W STOLBIK". pUSTX LT (n) |BITOWAQ SLOVNOSTX ALGORITMA tOOMA (W HUD[EM SLU^AE) DLQ UMNOVENIQ^ISEL DLINY n.
tOGDA ^ISLO OPERACIJ NA [AGE 2 NE PREWOSHODIT (2k ;1)LT ( nk ) + O(n), I POLU^A@]IESQ ^ISLA IME@T DLINU O(n).{AG 3. tAK KAK WSE xm | CELYE, TO WSE qm W FORMULE ( )RACIONALXNYE. pUSTX | IH OB]IJ ZNAMENATELX I qm = qm . tOGDA;1 h(x ). tAK KAK k | KONSTANTA,WSE qm | CELYE I cq = 1 P2km=1qmkmWSE qm | KONSTANTY PI DLINA WSEH ^ISEL h(xkm) ESTX O(n), TO DLQ;1 h(x ); q = 0; 1; : : : ; 2k ; 1, TREBUETSQWY^ISLENIQ WSEH SUMM 2km=1qmkmO(n) BITOWYH OPERACIJ I PRI \TOM POLU^A@TSQ ^ISLA DLINY O(n). tAKKAK | KONSTANTA, TO WY^ISLENIE WSEH cq (KOTORYE ZAWEDOMO DOLVNYBYTX CELYMI, KAK KO\FFICIENTY MNOGO^LENA h(x) = f (x)g(x)) TREBUETO(n) BITOWYH OPERACIJ (DELIM "W STOLBIK"), I WSE cq IME@T DLINUO(n).{AG 4.
wY^ISLENIE h(2km;1 ) SWODITSQ K SLOVENI@ ^ISEL Cq , SDWINUTYH WLEWO NE BOLEE, ^EM NA n RAZRQDOW. tAK KAK ^ISEL Cq KONSTANTNOEm;1KOLI^ESTWO, TO WY^ISLENIE h(2k ) = C = AB TREBUET O(n) BITOWYHOPERACIJ.dLQ OB]EGO ^ISLA LT (n) BITOWYH OPERACIJ W OPISANNOM ALGORITME (PRI n = km ) IMEEMLT (n) 6 (2k ; 1)LT ( nk ) + O(n):tOGDA PO TEOREME O REKURRENTNOM NERAWENSTWE DLQ WSEH n POLU^AEMC ROSTOM k IMEEMLT (n) = O(nlogk(2k;1)):logk (2k ; 1) = 1 + logk (2 ; 1 ) ;! 1:k20pO\TOMU DLQ L@BOGO " > 0 MOVNO WYBRATX k TAK, ^TO logk (2k ; 1) < 1+ "I LT (n) = O(n1+"). tEOREMA DOKAZANA.zAME^ANIE. e]E BOLEE BYSTRYM QWLQETSQ ALGORITM UMNOVENIQ ^ISEL {ENHAGE I {TRASSENA, BITOWAQ SLOVNOSTX KOTOROGO RAWNAO(n log n log log n).21aLGORITM {TRASSENA DLQ UMNOVENIQ MATRICrASSMOTRIM ZADA^U UMNOVENIQ DWUH KWADRATNYH MATRIC A =kaij k I B = kPbklnk PORQDKA n. pUSTX A B = C = kcrsk.
tOGDA PO OPREDELENI@ crs = p=1 arpbps. w KA^ESTWE WHODA MY BUDEM RASSMATRIWATX WSEZNA^ENIQ aij I bkl , S^ITAQ IH "NEDELIMYMI", TO ESTX MY WOSPRINIMAEMIH KAK EDINOE CELOE I NE MOVEM RABOTATX S KAKIMI-LIBO IH ^ASTQMI. wKA^ESTWE OPERACIJ BUDEM RASSMATRIWATX 4 ARIFMETI^ESKIE OPERACII,KOTORYE MOGUT PRIMENQTXSQ KAK K ISHODNYM PEREMENNYM aij ; bkl , TAKI K UVE POSTROENNYM WYRAVENIQM. nA[A ZADA^A SOSTOIT W POLU^ENIIWSEH WYRAVENIJ DLQ crs . sLOVNOSTX@ ALGORITMA BUDET S^ITATXSQ ^ISLOARIFMETI^ESKIH OPERACIJ.oBY^NYJ ALGORITM UMNOVENIQ MATRIC ("STRO^KA NA STOLBEC")TREBUET n3 UMNOVENIJ I n2(n ; 1) SLOVENIJ, TO ESTX PORQDKA n3 OPERACIJ.tEOREMA ({TRASSEN).
dLQ UMNOVENIQ DWUH MATRIC PORQDKAnlog7SU]ESTWUET ALGORITM S ^ISLOM ARIFMETI^ESKIH OPERACIJ O(n 2 ):dOKAZATELXSTWO oPI[EM TAKOJ ALGORITM. eSLI n| NE STEPENXDWOJKI I BLIVAJ[AQ K n SWERHU STEPENX DWOJKI ESTX 2k , TO RAS[IRIMDANNYE MATRICY A I B DO MATRIC A0 I B 0 PORQDKA 2k TAK, ^TOBY WLEWYH WERHNIH UGLAH MATRIC A0 I B 0 STOQLI, SOOTWETSTWENNO, A I B , AOSTALXNYE \LEMENTY BYLI RAWNY 0. tOGDA, ESLI A0 B 0 = C 0, TO LEGKOWIDETX, ^TO W C 0 W LEWOM WERHNEM UGLU STOIT MATRICA C = A B , AOSTALXNYE \LEMENTY RAWNY 0. pO\TOMU DLQ WY^ISLENIQ C = A BDOSTATO^NO PEREMNOVITX MATRICY A0 I B 0 PORQDKA 2k . pUSTX DALEEn = 2k | STEPENX DWOJKI I A; B | MATRICY PORQDKA n = 2k .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
