В.Б. Алексеев - Электронный коспект лекций, страница 4

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 . rAZREVEMKAVDU@ IZ MATRIC A I B , A TAKVE ISKOMU@ MATRICU C = A B , NA 4KWADRATNYH BLOKA RAZMERA n2 n2 :. B C11 A12 11 B12 11 C12 ;B = ;C = :A= AA21 A22B21 B22C21 C22 iZ ALGEBRY IZWESTNO, ^TO W \TOM SLU^AEC11 = A11B11 + A12B21; C12 = A11B12 + A12B22;C21 = A21B11 + A22B21; C22 = A21B12 + A22B22:tAKIM OBRAZOM, WY^ISLENIE MATRICY C SWODITSQ K 8 UMNOVENIQMMATRIC PORQDKA n2 (I NESKOLXKIM SLOVENIQM).

iDEQ {TRASSENA SOSTOITW ZAMENE 8 UMNOVENIJ NA 7 (SRAWNITE S ALGORITMOM kARACUBY). rAS-22SMOTRIM SLEDU@]IE 7 PROIZWEDENIJ:D1 = (A11 + A22)(B11 + B22); D5 = (A11 + A12)B22;D2 = (;A11 + A21)(B11 + B12); D6 = A22(;B11 + B21);D3 = (A12 ; A22)(B21 + B22); D7 = (A21 + A22)B11:D4 = A11(B12 ; B22);rASKRYWAQ SKOBKI I PRIWODQ PODOBNYE ^LENY, MOVNO PROWERITX, ^TOC11 = D1 + D3 ; D5 + D6; C12 = D4 + D5;C21 = D6 + D7;C22 = D1 + D2 + D4 ; D7:tAKIM OBRAZOM, UMNOVENIE MATRIC PORQDKA n SWODITSQ K 7 UMNOVENIQMMATRIC PORQDKA n2 I NESKOLXKIM SLOVENIQM MATRIC PORQDKA n2 : eSLIn = 2k ; TO \TOT PROCESS MOVNO PRODOLVITX REKURSIWNO. eSLI VE n = 1;TO DLQ UMNOVENIQ MATRIC PORQDKA 1 TREBUETSQ WSEGO 1 UMNOVENIE\LEMENTOW.

pUSTX L(n) | ^ISLO ARIFMETI^ESKIH OPERACIJ W OPISANNOMALGORITME. tAK KAK SLOVENIE DWUH MATRIC PORQDKA n2 TREBUET O(n2)OPERACIJ, TO DLQ n = 2k (k = 1; 2; 3; : : : ) POLU^AEM REKURRENTNOE NERAWENSTWOL(n) 6 7L( n2 ) + O(n2):pO TEOREME O REKURRENTNOM NERAWENSTWE OTS@DA POLU^AEM L(n) =O(nlog2 7): tEOREMA DOKAZANA.zAME^ANIE.