В.Б. Алексеев - Электронный коспект лекций (1158874), страница 3
Текст из файла (страница 3)
dLQ L@BYH i; j I k > 0-,,),(|..(k;1) (k;1)(k;1)d(k)ij = min(dij ; dik + dkj ):dOKAZATELXSTWO wSE PUTI IZ vi W Vj , ISPOLXZU@]IE TOLXKO WER[INYv1; v2; : : : ; vk , RASPADA@TSQ NA 2 MNOVESTWA A I B | NE PROHODQ]IH^EREZvk I PROHODQ]IH ^EREZ vk . mINIMALXNAQ DLINA PUTEJ W A RAWNA(k;1)dij PO OPREDELENI@.
kAVDYJ PUTX IZ B RAZBIWAETSQ NA 2 ^ASTI:PUTX B1 IZ vi W vk PO WER[INAM v1; v2; : : : ; vk;1 I PUTX B2 IZ vk Wvj PO WER[INAM v1; v2 ; : : : ; vk;1 . mINIMALXNAQ DLINA PUTI W B1 RAWNA.11d(kik ;1), A W B2 | d(kkj;1). sRAWNIWAQ d(kij ;1) I d(kik ;1) + d(kkj;1) , POLU^AEM d(k)ij .uTWERVDENIE DOKAZANO.zAME^ANIE. wY^ISLQQ d(k)ij OPISANNYM SPOSOBOM, MY, W ^ASTNOSTI, UZNAEM, ISPOLXZOWATX vk ILI NET.tAKIM OBRAZOM, DLQ WY^ISLENIQ D(k) PO D(k;1) DOSTATO^NO n2 SLOVENIJ I n2 SRAWNENIJ ^ISEL, A DLQ WY^ISLENIQ D(1); D(2); : : : ; D(n) = DPO ZADANNOJ MATRICE D = D(0) DOSTATO^NO n3 SLOVENIJ I n3 SRAWNENIJ.tEOREMA DOKAZANA.12mETOD "RAZDELQJ I WLASTWUJ". tEOREMA OREKURRENTNOM NERAWENSTWE.dRUGOJ REKURRENTNYJ METOD POSTROENIQ BYSTRYH ALGORITMOW |\TO METOD, KOTORYJ NAZYWA@T "RAZDELQJ I WLASTWUJ".
w NEM TAKVERE[ENIE ZADA^I SWODITSQ K RE[ENI@ PODZADA^, NO, W OTLI^IE OT METODADINAMI^ESKOGO PROGRAMMIROWANIQ, RAZMERNOSTX PODZADA^ OTLI^AETSQOT RAZMERNOSTI ZADA^I NE NA KONSTANTU, A W KONSTANTU RAZ I PODZADA^IRE[A@TSQ NEZAWISIMO DRUG OT DRUGA. dLQ POLU^ENIQ OCENOK SLOVNOSTITAKIH ALGORITMOW ISPOLXZUETSQ SLEDU@]AQ TEOREMA.tEOREMA (O REKURRENTNOM NERAWENSTWE). pUSTX L(n) MONOTONNO NEUBYWA@]AQ FUNKCIQ NATURALXNOGO PARAMETRA n pUSTX cNATURALXNOE ^ISLO c > 2 I a; b; DEJSTWITELXNYE KONSTANTYPRI^EM a > 0 I PUSTX DLQ WSEH n = ck GDE k L@BOE NATURALXNOE^ISLO (k = 1; 2; 3; : : : ) WYPOLNQETSQ NERAWENSTWOL(n) 6 aL( nc ) + bn:(6)tOGDA PRI STREMLENII n K BESKONE^NOSTI DLQ WSEH n WYPOLNQETSQ8>ESLI > logc a<O (n );L(n) = >O(nlogc a); ESLI < logc a(7):O(n log n); ESLI = logc a|.,,-,-|,,-,,,.dOKAZATELXSTWO.
pUSTX n = ck , GDE k = 1; 2; 3; : : : . tOGDA, PRIMENQQNESKOLXKO RAZ (6), POLU^AEM nnL(n) 6 aL( c ) + bn 6 a(aL( c2 ) + b nc ) + bn =n + a2L n 6cc2 ann26 bn + b c n + a (aL c3 + b c2 ) =2 aa3= bn + bn + bn + a L n3 6ccck;1aank6 : : : 6 bn + bn c + : : : + bn c + a L ck :pUSTX d = max(b; L(1)). tAK KAK cnk = 1, TO2k;1 aaaL(n) 6 dn 1 + c + c + : : : + c+ dak == bn + ab132kaaa1+ + ++ :cccrASSMOTRIM 3 SLU^AQ:a1) logc a < =) < 1 =) L(n) 6 dn const = O(n);ca2) logc a > =) > 1 =)c!k c 2 kacc=)=) L(n) 6 dn 1+ +caa ++ a= dn(8)=) L(n) 6 dak const = O(alogc n) = O(nlogc a) (TAK KAK alogc n = nlogc a);3) logc a = =) a = c =) L(n) 6 dn(k + 1) = dn(1 + logc n) == O(n log n):pUSTX TEPERX n | L@BOE.
tOGDA SU]ESTWUET NATURALXNOE k, TAKOE,^TO ck < n 6 ck+1. rASSMOTRIM 3 SLU^AQ, U^ITYWAQ, ^TO PO USLOWI@L(n) | NEUBYWA@]AQ FUNKCIQ:1) > logc a =) L(n) 6 L(ck+1) 6 p(ck+1) = pc(ck ) 6 pc n == O(n);2) < logc a =) L(n) 6 L(ck+1) 6 p(ck+1)logc a = pclogc a(ck )logc a 66 panlogc a = O(nlogc a);(9)k+1k3) = logc a =) L(n) 6 L(c ) 6 pc 2k(c ) 6 pc 2n logc n == O(n) log n:tEOREMA DOKAZANA.{z|6const14}~ASTX 2. sHEMYx 6.
rEALIZACIQ NEKOTORYH \ARIFMETI^ESKIH"SISTEM fal W KLASSE sf|rASSMOTRIM TEPERX NEKOTORYE \ARIFMETI^ESKIE" SISTEMY falI POSTROIM REALIZU@]IE IH sf|.sISTEMY Sn, Mn I Wn , SOSTOQ]IE IZ (n + 1), 2n I n fal OT bpx = (x1; : : : ; xn); y = (y1; : : : ; yn) SOOTWETSTWENNO, TAKIE, ^TOjSn(x; y)j = jxj + jyj; jMn(x; y)j = jxj jyj;I, ESLI jxj > jyj, TOjWn(x; y)j = jxj ; jyj;NAZYWA@TSQ (FUNKCIONALXNYM) SUMMATOROM UMNOVITELEM I WY^ITATELEM PORQDKA n SOOTWETSTWENNO.sISTEMA Cn, SOSTOQ]AQ IZ (n + 1) fal OT bp x = (x1; : : : ; x2n ),TAKAQ, ^TO ZNA^ENIE jCn(x)j RAWNO ^ISLU EDINIC W NABORE x, NAZYWAETSQ(FUNKCIONALXNYM) S^ET^IKOM PORQDKA n.w [8] PRIWEDEN SUMMATOR PORQDKA n, IME@]IJ SLOVNOSTX 9n ; 5.mY POSTROIM TAKOJ VE SUMMATOR NESKOLXKO INA^E.tEOREMA 6.1.
sU]ESTWUET SHEMNYJ SUMMATOR PORQDKA n IME@]IJ SLOVOSTX 9n ; 5dOKAZATELXSTWO dLQ n = 1 SUMMATOR 1 POKAZAN NA RIS. 4.4. nARIS. 6.1.A POKAZANA sf| 0 SLOVNOSTI 9, KOTORAQ REALIZUET SISTEMUfal S 0 OT bp x; y I q0 TAKU@, ^TOjS 0 (x; y; q0 )j = x + y + q0 ;T. E. REALIZUET SLOVENIE TREH ODNORAZRQDNYH ^ISEL. dEJSTWITELXNO, NAWYHODE z2 sf| 0 REALIZUETSQ fal x y q0 , A NA WYHODE z1 EDINICAPOQWLQETSQ TOLXKO TOGDA, KOGDA LIBO x = y = 1, LIBO x y = q0 = 1,T. E. NA WYHODE z1 W sf| 0 REALIZUETSQ falxy _ (x y)q0 = xy _ xq0 _ yq0:sHEMNYJ SUMMATOR n PORQDKA n S WHODNYMI bp x1; : : : ; xn; y1; : : : ; ynI WYHODNYMI bp z0; z1; : : : ; zn MOVNO POSTROITX IZ SUMMATORA n;1PORQDKA (n ; 1) S WHODNYMI bp x2; : : : ; xn; y2; : : : ; yn I WYHODNYMI bpz10 ; z2; : : : ; zn, A TAKVE ODNOJ sf| 0 TAK, KAK \TO POKAZANO NA RIS.
6.2.zAMETIM, ^TO PEREHOD OT SUMMATORA n;1 K SUMMATORU n MODELIRUET,-,..15-SLOVENIE n-RAZRQDNYH ^ISEL W DWA \TAPA: NA PERWOM \TAPE SKLADYWA@TSQ ^ISLA, OBRAZUEMYE (n ; 1) MLAD[IMI RAZRQDAMI, A NA WTOROM\TAPE SKLADYWA@TSQ STAR[IE RAZRQDY I PERENOS, WOZNIK[IJ NA PERWOM\TAPE.
o^EWIDNO, ^TOL(n) = 9n ; 5:tEOREMA DOKAZANA.sLEDSTWIE. L(Sn) 6 9n ; 5:tEOREMA 6.2. sU]ESTWUET SHEMNYJ WY^ITATELX PORQDKA nIME@]IJ SLOVNOSTX NE BOLX[E ^EM 11n ; 5dOKAZATELXSTWO zAMETIM, ^TOjxj = 2n ; 1 ; jxj;GDE x = (x1; : : : ; xn), x = (x1; : : : ; xn), I PO\TOMUWn(x; y) = jxj ; jyj = 2n ; 1 ; (2n ; 1 ; jxj + jyj) = S n(x; y)sLEDOWATELXNO, SHEMNYJ WY^ITATELX PORQDKA n MOVET BYTX POLU^ENIZ SHEMNOGO SUMMATORA PORQDKA n W REZULXTATE INWERTIROWANIQ WHODOWEGO PERWOGO SLAGAEMOGO, A TAKVE WSEH EGO WYHODOW, I IMEET SLOVNOSTXNE BOLX[E, ^EM 11n ; 5.tEOREMA DOKAZANA.rASSMOTRIM TEPERX SLOVNOSTX UMNOVITELQ Mn DLQ UMNOVENIQ DWUH NEOTRICATELXNYH n-RAZRQDNYH DWOI^NYH ^ISEL X =j(x1; x2; : : : ; xn )j I Y = j(y1; y2; : : : ; yn)j.
tAK KAK X < 2n I Y < 2n,TO XY < 22n I DLQ PREDSTAWLENIQ REZULXTATA TREBUETSQ NE BOLEE 2nWYHODOW. oBOZNA^IM ^EREZ LM (n) NAIMENX[EE WOZMOVNOE ^ISLO \LEMENTOW W UMNOVITELE Mn. o^EWIDNO, ^TO LM (1) = 1, TAK KAK UMNOVENIE1-RAZRQDNYH ^ISEL OSU]ESTWLQET \LEMENT KON_@NKCIQ.uTWERVDENIE. sU]ESTWUET sf| DLQ UMNOVENIQ n RAZRQDNOGO^ISLA X NA RAZRQDNOE ^ISLO y S ^ISLOM \LEMENTOW ndEJSTWITELXNO, ESLI X = j(x1; x2; : : : ; xn)j I Xy = Z =j(z1; z2; : : : ; zn )j, TO zi =xiy DLQ WSEH i = 1; 2; : : : ; n.pRI UMNOVENII DWUH n-RAZRQDNYH ^ISEL X I Y \W STOLBIK" NADOn RAZ UMNOVITX X NA 1-RAZRQDNOE ^ISLO (WSEGO n2 KON_@NKCIJ) I ZATEMn ; 1 RAZ SLOVITX ^ISLA DLINOJ NE BOLEE 2n. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
