Алексеев - Сложность алгоритмов (1123759), страница 4
Текст из файла (страница 4)
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.
oVIDAETSQ, ^TO DLQ UMNOVENIQ MATRIC PORQDKA nSU]ESTWUET ALGORITM S ^ISLOM ARIFMETI^ESKIH OPERACIJ O(n2+") DLQL@BOGO FIKSIROWANNOGO " > 0 (SRAWNITE S ALGORITMOM tOOMA), ODNAKOPOKA (SEREDINA 2001 GODA) NAILU^[EJ OCENKOJ QWLQETSQ O(n2:38) [ ].23aLGORITMY UMNOVENIQ 0-1-MATRICpUSTX MATRICY A I B SOSTOQT TOLXKO IZ 0 I 1 I TREBUETSQWY^ISLITX C = A B; GDE WSE \LEMENTY crs DOLVNY BYTX PREDSTAWLENYW DWOI^NOJ SISTEME. w KA^ESTWE OPERACIJ RAZRE[IM TOLXKO L@BYEBITOWYE OPERACII NAD DWUMQ PEREMENNYMI.tEOREMA.
dLQ WY^ISLENIQ OBY^NOGO PROIZWEDENIQ DWUHMATRIC PORQDKA n SU]ESTWUET ALGORITM S ^ISLOM BITOWYH OPERACIJ O(nlog2 7 log2 n):lEMMA. eSLI W ISHODNYH MATRICAH A I B PORQDKA n WSE \LEMENTY IME@T DWOI^NU@ DLINU NE BOLEE k WKL@^AQ ZNAK TO W ALGORITME {TRASSENA DLQ WY^ISLENIQ AB WSE WOZNIKA@]IE ^ISLA IME@TDWOI^NU@ DLINU NE BOLEE 2k + 4dlog2 ne:dOKAZATELXSTWO LEMMY pRI FORMIROWANII PODZADA^ WY^ISLENIQ D1 ; D7 W ALGORITME {TRASSENA PROISHODIT SLOVENIE (ILI WY^ITANIE) NE BOLEE ^EM DWUH MATRIC. pO\TOMU MODULI WSEH ^ISEL NEBOLEE ^EM UDWAIWA@TSQ, TO ESTX DOBAWLQETSQ NE BOLEE ODNOGO RAZRQDA.pRI PEREHODE OT RAZMERNOSTI n K RAZMERNOSTI 1 PODZADA^I FORMIRU@TSQ dlog2 ne RAZ.
sLEDOWATELXNO, W PODZADA^AH RAZMERNOSTI 1 WSE^ISLA IME@T DLINU NE BOLEE k + dlog2 ne: dLQ PODZADA^ RAZMERNOSTI 1ALGORITM {TRASSENA PROIZWODIT OBY^NOE UMNOVENIE. pRI \TOM DLINAPOLU^A@]IHSQ ^ISEL NE PREWOSHODIT 2k +2dlog2 ne: pRI WY^ISLENII CrsPO REZULXTATAM PODZADA^ D1 ; D7 SKLADYWA@TSQ (WY^ITA@TSQ) NE BOLEE^EM PO 4 MATRICY. pRI \TOM MAKSIMALXNYE MODULI ^ISEL WOZRASTA@TNE BOLEE ^EM W 4 RAZA, TO ESTX DOBAWLQETSQ NE BOLEE ^EM PO 2 RAZRQDA.pOSKOLXKU OBRATNYH [AGOW TAKVE dlog2 ne; TO WSE POLU^AEMYE ^ISLAIME@T DLINU NE BOLEE 2k + 2dlog2 ne + 2dlog2 ne = 2k + 4dlog2 ne: lEMMADOKAZANA.dOKAZATELXSTWO TEOREMY pRIMENIM DLQ WY^ISLENIQ AB ALGORITM {TRASSENA. pO USLOWI@ W ISHODNYH MATRICAH A I B WSE \LEMENTYIME@T DLINU 2 (WKL@^AQ ZNAK).
tOGDA PO LEMME WSE WOZNIKA@]IE WALGORITME ^ISLA BUDUT IMETX DLINU NE BOLEE 4 + 4dlog2 ne = O(log n):tAK KAK W ALGORITME {TRASSENA ISPOLXZU@TSQ TOLXKO SLOVENIE, WY^ITANIE I UMNOVENIE, TO L@BAQ ARIFMETI^ESKAQ OPERACIQ W ALGORITME{TRASSENA TREBUET O(log2 n) BITOWYH OPERACIJ. pOSKOLXKU ALGORITM{TRASSENA ISPOLXZUET O(nlog2 7) ARIFMETI^ESKIH OPERACIJ, TO WSE ONIPOTREBU@T O(nlog2 7 log2 n) BITOWYH OPERACIJ. tEOREMA DOKAZANA.zAME^ANIE 1. oCENKU MOVNO ULU^[ITX, ESLI ISPOLXZOWATX BYSTRYE ALGORITMY DLQ UMNOVENIQ ^ISEL.zAME^ANIE 2. w \TOJ TEOREME MOVNO POLU^ITX OCENKU O(n2:38);()0-1---(..24),-ESLI ISPOLXZOWATX IZWESTNYJ BOLEE BYSTRYJ ALGORITM UMNOVENIQ MATRIC.rASSMOTRIM TEPERX OPERACI@ BULEWSKOGO UMNOVENIQ 0-1-MATRIC.oPREDELENIE.
pUSTX A = kaij k I B = kbklk DWE MATRICYPORQDKA n: bULEWSKIM PROIZWEDENIEM A B NAZYWAETSQ MATRICA D =kdrsk TAKAQ ^TOn_drs = arp bps|0-1-,p=1DLQ WSEH r I sdLQ BULEWSKOGO UMNOVENIQ MATRIC NELXZQ NEPOSREDSTWENNO PRIMENITX IDE@ {TRASSENA, TAK KAK W ALGORITME {TRASSENA ESTX WY^ITANIE, A U DIZ_@NKCII NET OBRATNOJ OPERACII. nESMOTRQ NA \TO,SPRAWEDLIWA SLEDU@]AQ TEOREMA.tEOREMA. bULEWSKOE PROIZWEDENIE D = A B DWUH MATRICA I B PORQDKA n MOVNO WY^ISLITX S ^ISLOM BITOWYH OPERACIJO(nlog2 7 log2 n)dOKAZATELXSTWO mY OPI[EM SOOTWETSTWU@]IJ ALGORITM, KOTORYJ OSNOWAN NA IDEE "RAS[IRENIQ MODELI" (SM.
ALGORITM tOOMA).wMESTO WY^ISLENIQ D = A B MY WY^ISLIM SNA^ALA OBY^NOE PROIZWEDENIE C = AB . pRI \TOM OTMETIM SLEDU@]U@ SWQZX MEVDU D IC:drs = 1 () crs > 0:pO PREDYDU]EJ TEOREME DLQ WY^ISLENIQ C = kcrs k SU]ESTWUET ALGORITM S ^ISLOM BITOWYH OPERACIJ O(nlog2 7 log2 n): pOSLE \TOGO W KAVDOM crs DOSTATO^NO WZQTX DIZ_@NKCI@ WSEH RAZRQDOW (ISKL@^AQ ZNAK),^TOBY WY^ISLITX drs: pOSKOLXKU 0 6 crs 6 n, TO DLINA KAVDOGO crsNE PREWOSHODIT O(log n) I NA WY^ISLENIE WSEH drs IZ crs POTREBUETSQO(n2 log n) BITOWYH OPERACIJ.
oB]EE ^ISLO BITOWYH OPERACIJ BUDETO(nlog2 7 log2 n) + O(n2 log n) = O(nlog2 7 log2 n): tEOREMA DOKAZANA.zAME^ANIE. sM. ZAME^ANIQ K PREDYDU]EJ TEOREME..0-1-..25tRANZITIWNOE ZAMYKANIE GRAFOWdANO: ORIENTIROWANNYJ GRAF G W WIDE MATRICY A = kaij k, GDEaij = 1, ESLI W G ESTX DUGA IZ vi W vj , I aij = 0, ESLI TAKOJ DUGI NET(aii = 0 DLQ WSEH i).tREBUETSQ: POSTROITX MATRICU B = kbij k, TAKU@, ^TO bij = 1, ESLIESTX ORIENTIROWANNYJ PUTX IZ vi W vj , I bij = 0, ESLI TAKOGO PUTI NET(W ^ASTNOSTI, bii = 1 DLQ WSEH i).oPREDELENIE.
oRIENTIROWANNYJ GRAF S MATRICEJ SMEVNOSTIB NAZYWAETSQ TRANZITIWNYM ZAMYKANIEM GRAFA GtEOREMA. tRANZITIWNOE ZAMYKANIE ORIENTIROWANNOGOGRAFA S3log7n WER[INAMI MOVNO POSTROITX ISPOLXZUQ O(n 2 log n) BITOWYHOPERACIJdOKAZATELXSTWO pUSTX A | MATRICA SMEVNOSTI ORGRAFA GI MATRICA A = kaij k POLU^AETSQ IZ A ZAMENOJ WSEH DIAGONALXNYH\LEMENTOW NA 1. tOGDA aij = 1 W TOM I TOLXKO W TOM SLU^AE, ESLI IZvi W vj SU]ESTWUET ORIENTIROWANNYJ PUTX DLINY (T.E. S ^ISLOM DUG) NEBOLEE 1. pUSTX Ak = A A : : : A; GDE ^ISLO SOMNOVITELEJ RAWNO k IUMNOVENIE MATRIC BULEWSKOE.lEMMA. eSLI Ak = kakij k; TO akij = 1 W TOM I TOLXKO W TOMSLU^AE ESLI W G SU]ESTWUET ORIENTIROWANNYJ PUTX IZ vi W vj DLINYNE BOLEE kdOKAZATELXSTWO (INDUKCIEJ PO k). pRI k = 1 UTWERVDENIE WERNO.pUSTX ONO WERNO PRI k = p, TO ESTX apij = 1 TOGDA I TOLXKO TOGDA, KOGDASU]ESTWUET PUTX IZ vi W vj WDLINY NE BOLEE p.
pO OPREDELENI@ POLU^AEMpp+1A(p+1) = Ap A I ap+1ij = q aiq aqj . oTS@DA aij = 1 TOGDA I TOLXKOTOGDA, KOGDA SU]ESTWUET WER[INA vq TAKAQ, ^TO IZ vi W vq SU]ESTWUETPUTX DLINY NE BOLEE p, I IZ vq W vj SU]ESTWUET PUTX DLINY NE BOLEE1. nO \TO USLOWIE RAWNOSILXNO TOMU, ^TO IZ vi W vj SU]ESTWUET PUTXDLINY NE BOLEE p + 1. tAKIM OBRAZOM, UTWERVDENIE LEMMY WERNO I PRIk = p + 1. lEMMA DOKAZANA.eSLI W ORGRAFE G IZ vi W vj SU]ESTWUET HOTQ BY ODIN ORIENTIROWANNYJ PUTX, TO SU]ESTWUET TAKOJ PUTX BEZ POWTORENIQ WER[IN I, SLEDOWATELXNO, DLINY NE BOLEE n ; 1, GDE n | ^ISLO WER[IN W G. pO\TOMUIZ LEMMY SLEDUET, ^TO Ak = B PRI L@BOMk > n ; 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
