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

tAKIM OBRAZOM, ALGORITM MOVNO PREDSTAWITX W WIDEBINARNOGO KORNEWOGO DEREWA, W KOTOROM KAVDOJ WER[INE, OTLI^NOJ OTLISTXEW, PRIPISANA PARA NOMEROW SRAWNIWAEMYH \LEMENTOW, A LISTXQMPRIPISANY OTWETY W WIDE PERESTANOWOK (i1; i2; : : : ; in).oPREDELENIE. sLOVNOSTX@ LA(n) ALGORITMA SORTIROWKI ANAZYWAETSQ MAKSIMALXNOE ^ISLO WOPROSOW OT NA^ALA RABOTY DO OTWETA GDE MAKSIMUM BERETSQ PO WSEM WOZMOVNYM WHODNYM POSLEDOWATELXNOSTQM DLINY n sLOVNOSTX@ SORTIROWKI n \LEMENTOWLSORT(n) NAZYWAETSQ min LA(n) GDE MINIMUM BERETSQ PO WSEM ALGORITMAM SORTIRU@]IM PRAWILXNO n \LEMENTOWtEOREMA.

dLQ L@BOGO ALGORITMA A SORTIRU@]EGO n \LEMENTOW WYPOLNQETSQ NERAWENSTWO LA(n) > log2 n!dOKAZATELXSTWO aLGORITM A MOVNO PREDSTAWITX W WIDE BINARNOGO DEREWA D. l@BAQ PERESTANOWKA (i1; i2; : : : ; in) \LEMENTOW 1; 2; : : : ; nMOVET BYTX OTWETOM W ALGORITME I, SLEDOWATELXNO, DOLVNA BYTX PRIPISANA HOTQ BY ODNOMU LISTU.

pO\TOMU W DEREWE D NE MENEE n! LISTXEW.oTS@DA PO LEMME POLU^AEM, ^TO WYSOTA DEREWA h(D) > log2 n!. nO, POOPREDELENI@ LA(n) = h(D). tEOREMA DOKAZANA.sLEDSTWIE. LSORT(n) > log2 n!iSPOLXZUQ FORMULU STIRLINGA DLQ n!, POLU^AEMsLEDSTWIE. LSORT(n) > (1 ; o(1))n log2 n ILI LSORT(n) &-,-.,-,.,,-...n log2 n().rASSMOTRIM DALEE 2 ALGORITMA SORTIROWKI, SLOVNOSTX KOTORYHBLIZKA K POLU^ENNOJ NIVNEJ OCENKE.5sORTIROWKA WSTAWKAMIpOSLEDOWATELXNO RE[AEM PODZADA^I: OTSORTIROWATX a1; : : : ; an PRIk = 1; 2; : : : ; n. pRI k = 1 (BAZIS) OTWET TRIWIALEN, PRI k = n POLU^AEMOTWET WSEJ ZADA^I. pEREHOD OT PODZADA^I S PARAMETROM k ; 1 K kPROISHODIT PUTEM WSTAWKI W UVE UPORQDO^ENNU@ POSLEDOWATELXNOSTXai1 < ai2 < : : : < aik;1 \LEMENTA ak NA SOOTWETSTWU@]EE MESTO.

pRI \TOMDLQ ak IMEETSQ k WOZMOVNYH POLOVENIJ: PERED ai1 , MEVDU ai1 I ai2 ,: : : ,POSLE aik;1 .wSTAWKA ak NA NUVNOE MESTO OSU]ESTWLQETSQ BINARNYM POISKOM.tEOREMA. sLOVNOSTX ALGORITMA SORTIROWKI WSTAWKAMILWST(n) UDOWLETWORQET NERAWENSTWU LWST(n) 6 log2 n! + n ; 1dOKAZATELXSTWO tAK KAK PRI WSTAWKE \LEMENTA ak WNA^ALE IMEETSQ k WOZMOVNYH POLOVENIJ: PERED ai1 ,MEVDU ai1 I ai2 ,: : : ; POSLEaik;1 , TO DLQ WSTAWKI ak BINARNYM POISKOM NUVNO SDELATX NE BOLEEdlog2 ke SRAWNENIJ.

wESX ALGORITM TREBUET SRAWNENIJ NE BOLEE dlog2 2e+dlog2 3e + dlog2 4e + : : : + dlog2 ne 6 log2 2 + log2 3 + : : : + log2 n + (n ; 1) =log2 n! + n ; 1.sLEDSTWIE. WST(n) 6 (1 + o(1))n log2 n PRI n ! 1sLEDSTWIE. SORT(n) n log2 n PRI n ! 1pOSLEDNEE SLEDSTWIE WYTEKAET IZ SLEDSTWIJ IZ TEOREM 1 I 2.sORTIROWKA SLIQNIEMsORTIROWKA SLIQNIEM n \LEMENTOW OPISYWAETSQ REKURSIWNO. eSLIn = 1, TO ZADA^A TRIWIALXNA. dLQ n > 2 DELIM POSLEDOWATELXNOSTXa1; a2; : : : ; an NA 2 POSLEDOWATELXNOSTI a1; a2; : : : ; ab n2 c , SORTIRUEM TEM VEALGORITMOM SORTIROWKI SLIQNIEM KAVDU@ IZ PODPOSLEDOWATELXNOSTEJI ZATEM SLIWAEM 2 POLU^ENNYE OTSORTIROWANNYE POSLEDOWATELXNOSTIA = (ai1 < ai2 < : : : < aib n2 c) I B = (aj1 < aj2 < : : : < ajn;b n2 c ), FORMIRUQOTSORTIROWANNU@ POSLEDOWATELXNOSTX C .

nA KAVDOM [AGE SLIQNIQ MYSRAWNIWAEM PERWYE \LEMENTY IZ A I B I PERENOSIM MENX[IJ IZ NIHO^EREDNYM \LEMENTOM W C (ESLI A ILI B STANOWITSQ PUSTYM, TO PERENOSIM OSTAW[IESQ \LEMENTY W C PO PORQDKU). pUSTX LSL(n) | SLOVNOSTX(^ISLO SRAWNENIJ) ALGORITMA SORTIROWKI SLIQNIEM DLQ n \LEMENTOW WHUD[EM SLU^AE.

tOGDA LSL(1) = 0 I LSL(n) = LSL(b n2 c)+LSL(d n2 e)+n;1PRI n > 2, POSKOLXKU NA SLIQNIE W HUD[EM SLU^AE MOVET POTREBOWATXSQn ; 1 SRAWNENIJ.lEMMA. LSL(n) = n log2 n ; n + 1 DLQ n = 2k GDE k L@BOENATURALXNOE ^ISLO ILI k = 0dOKAZATELXSTWO (INDUKCIEJ PO k).

pRI k = 0 POLU^AEM WERNOERAWENSTWO LSL(1) = 0. pUSTX UTWERVDENIE LEMMY WERNO PRI WSEH..L.L.,.6-0 6 k 6 m ; 1, GDE m - NATURALXNOE ^ISLO. tOGDA DLQ k = m IMEEMLSL(2m ) = 2LSL(2m;1) + 2m ; 1 = 2(2m;1 (m ; 1) ; 2m;1 + 1) + 2m ; 1 =m2m ; 2m + 1, TO ESTX DLQ k = m UTWERVDENIE LEMMY TAKVE WERNO.sLEDOWATELXNO, ONO WERNO DLQ WSEH NATURALXNYH k.tEOREMA. LSL(n) < 2n log2 n + 1 DLQ WSEH NATURALXNYH ndOKAZATELXSTWO uTWERVDENIE TEOREMY SPRAWEDLIWO PRI n = 1.dLQ L@BOGO NATURALXNOGO n > 2 NAJDETSQ NATURALXNOE k TAKOE, ^TO2k;1 < n 6 2k . fUNKCIQ LSL(n), O^EWIDNO, NE UBYWAET S ROSTOM n.pO\TOMU LSL(n) 6 LSL(2k ) = 2k k ; 2k +1 = 2k (k ; 1)+1 < 2n log2 n +1.tEOREMA DOKAZANA...7rEKURRENTNYE METODY POSTROENIQ ALGORITMOW.mETOD DINAMI^ESKOGO PROGRAMMIROWANIQoDNO IZ WAVNYH NAPRAWLENIJ W POSTROENII BYSTRYH ALGORITMOW| \TO REKURRENTNYE METODY.

pRI \TOM RE[ENIE ZADA^I SWODITSQ KRE[ENI@ BOLEE PROSTYH PODZADA^ TAKOGO VE TIPA, KOTORYE, W SWO@O^EREDX, SWODQTSQ K E]E BOLEE PROSTYM PODZADA^AM I T.D. eSTESTWENNOPRI \TOM DOLVEN BYTX NEKOTORYJ BAZISNYJ UROWENX, ZADA^I KOTOROGORE[A@TSQ UVE NE REKURRENTNO, A NEPOSREDSTWENNO. mOVNO WYDELITX 2OSNOWNYH REKURRENTNYH METODA, KOTORYE ISPOLXZU@TSQ DLQ POSTROENIQ BYSTRYH ALGORITMOW: METOD DINAMI^ESKOGO PROGRAMMIROWANIQ IMETOD "RAZDELQJ I WLASTWUJ".w SAMOM [IROKOM WIDE IDEQ DINAMI^ESKOGO PROGRAMMIROWANIQ SOSTOIT W WYDELENII W DANNOJ ZADA^E S PARAMETROM n (HARAKTERIZU@]IMDLINU WHODA) PODZADA^ S MENX[IMI PARAMETRAMI I RE[ENII PODZADA^W SOOTWETSTWII S UWELI^ENIEM PARAMETRA, NA^INAQ S SAMOGO MENX[EGO(OBY^NO 0 ILI 1).

pRI \TOM ZADA^A S PARAMETROM k RE[AETSQ, KOGDA UVERE[ENY WSE PODZADA^I S PARAMETROM k ; 1 I MENX[E (INOGDA NE k ; 1, Ak ; c, GDE c | KONSTANTA). pRI \TOM BOLX[OGO ^ISLA PODZADA^ UDAETSQ^ASTO IZBEVATX ZA S^ET TOGO, ^TO RE[ENIE RAZNYH PODZADA^ SWODITSQ KRE[ENI@ ODNIH I TEH VE PODZADA^. rASSMOTRIM PRIMERY.zADA^A OB OPTIMALXNOM PORQDKE UMNOVENIQ MATRIC.mY BUDEM RASSMATRIWATX ZDESX TOLXKO OBY^NYJ SPOSOB UMNOVENIQ DWUH MATRIC ("STRO^KA NA STOLBEC") I BUDEM U^ITYWATX TOLXKO^ISLO UMNOVENIJ \LEMENTOW. pRI \TOM ESLI MATRICY A I B IME@TRAZMERY m n I n p, TO DLQ WY^ISLENIQ A B TREBUETSQ, O^EWIDNO,mnp UMNOVENIJ \LEMENTOW.

iZWESTNO, ^TO DLQ L@BYH TREH MATRIC(AB )C = A(BC ), TO ESTX PROIZWEDENIE MATRIC NE ZAWISIT OT RASSTANOWKI SKOBOK. oDNAKO ^ISLO OPERACIJ UMNOVENIQ \LEMENTOW MOVET PRI\TOM OKAZATXSQ RAZNYM.pRIMER. pUSTX MATRICY A; B; C IME@T RAZMERY n1; 1n; nn.tOGDA MATRICA AB IMEET RAZMERY n n I PRI WY^ISLENII (AB )C ISPOLXZUETSQ n2 + n3 UMNOVENIJ \LEMENTOW.

mATRICA BC IMEET RAZMERY1 n, PO\TOMU PRI WY^ISLENII A(BC ) ISPOLXZUETSQ n2 + n2 = 2n2UMNOVENIJ \LEMENTOW, ^TO PRIMERNO W n2 RAZ MENX[E, ^EM DLQ (AB )C .tAKIM OBRAZOM, IMEET SMYSL SLEDU@]AQ ZADA^A.zADA^A. wHOD: NABOR NATURALXNYH ^ISEL (m0; m1; : : : ; mn) (KOTORYJ ZADAET RAZMERY MATRIC W PROIZWEDENII A1A2 : : : An, GDE Ai IMEETRAZMERY mi;1 mi ).8tREBUETSQ: rASSTAWITX SKOBKI W PROIZWEDENII A1 A2 : : : AnTAK, ^TOBY OB]EE ^ISLO UMNOVENIJ \LEMENTOW BYLO MINIMALXNYM, IWY^ISLITX \TO MINIMALXNOE ^ISLO.pOSMOTRIM SNA^ALA, KAKOWA SLOVNOSTX TRIWIALXNOGO ALGORITMA,KOTORYJ PEREBIRAET WSE SPOSOBY RASSTANOWKI SKOBOK.

pUSTX an | ^ISLOSPOSOBOW PRAWILXNOJ RASSTANOWKI SKOBOK W PROIZWEDENII A1 A2 : : : An.(2n;2)! PRI n > 2tEOREMA. an = n1 C2nn;;12 = n!(n;1)!dOKAZATELXSTWO o^EWIDNO, ^TO a1 = 1, a2 = 1, a3 = 2. oPERACIQ,KOTORU@ MY SDELAEM POSLEDNEJ W A1 A2 : : : An, SWODIT ZADA^U K 2PODZADA^AM A1 : : : Ak I Ak+1 : : : An, GDE 1 6 k 6 n ; 1. pO\TOMU..an = a1an;1 + a2an;2 + : : : + an;1a1:rASSMOTRIM PROIZWODQ]U@ FUNKCI@f (x) = a1x + a2x2 + a3x3 + : : : + anxn + : : : ()tOGDAf 2(x) = (a1a1)x2 + (a1a2 + a2a1)x3 + (a1a3 + a2a2 + a3a1)x4 + : : : =(1)a2x2 + a3x3 + a4x4 + : : : = f (x) ; a1x = f (x) ; x:(2)tAKIM OBRAZOM, f 2(px) ; f (x) + x = 0.

rE[AQ KWADRATNOE pURAWNENIE,POLU^AEM f (x) = 1 12;4x . pOSKOLXKU f (0) = 0, TO f (x) = 1; 12;4x . rASKLADYWAQ f (x) W RQD tEJLORA I SRAWNIWAQ S ( ), POLU^AEM (PROWERXTE):n;1(3)an = 21 32 25 : : : 2n 2; 3 4n! =2n;12n;1 (2n ; 2)!(1 3 5 : : : (2n ; 3)) =n!n!(2 4 6 (2n ; 2)) = (4)2n;1(2n ; 2)! = 1 C n;1 :(5)n!2n;1(n ; 1)! n 2n;2tEOREMA DOKAZANA.zAME^ANIE dLQ POLNOJ STROGOSTI W DOKAZATELXSTWE NUVNO OBSUDITX SU]ESTWOWANIE FUNKCII f (x), ZADANNOJ RAWENSTWOM ().

mOVNOPOKAZATX, ^TO RQD SPRAWA SHODITSQ, NAPRIMER, PRI 0 6 x 6 41 .rASKRYWAQFAKTORIALY PO FORMULE sTIRLINGA, LEGKO POLU^ITX,qm 2p22m = p4m , TO ESTX an RASTET \KSPONENCIALXNO S ROS^TO C2m 2mmTOM n. sLEDOWATELXNO PEREBORNYJ ALGORITM IMEET \KSPONENCIALXNU@SLOVNOSTX..9tEOREMA. dLQ NAHOVDENIQ OPTIMALXNOGO PORQDKA UMNOVENIQ nMATRIC SU]ESTWUET ALGORITM TIPA DINAMI^ESKOGO PROGRAMMIROWANIQ S ^ISLOM OPERACIJ ARIFMETI^ESKIH I SRAWNENIJ ^ISEL O(n3)dOKAZATELXSTWO pUSTX NA WHOD POSTUPAET NABOR ^ISEL(m0; m1; : : : ; mn). wWEDEM TAKIE PODZADA^I Bij : NAJTI OPTIMALXNYJPORQDOK WY^ISLENIJ I NAIMENX[EE ^ISLO kij UMNOVENIJ \LEMENTOW DLQPROIZWEDENIQ Ai Ai+1 : : : Aj , (1 6 i 6 j 6 n). o^EWIDNO, kii = 0DLQ WSEH i, I OB]EE ^ISLO PODZADA^ Bij ESTX O(n2).uTWERVDENIE.

eSLI 1 6 i < j 6 n TOkij = minfki;i+s + ki+s+1;j + mi;1 mi+s mj g; ()GDE MINIMUM BERETSQ PO WSEM s TAKIM ^TO 0 6 s 6 j ; i ; 1dOKAZATELXSTWO eSLI POSLEDNQQ OPERACIQ UMNOVENIQ DELITPROIZWEDENIE Ai A2 : : : Aj NA 2 PROIZWEDENIQ (Ai : : : Ai+s ) (Ai+s+1 : : : Aj ), TO DLQ POLU^ENIQ MINIMALXNOGO ^ISLA OPERACIJ NADO ISPOLXZOWATX MINIMALXNOE ^ISLO OPERACIJ W OBEIH SKOBKAH, TO ESTX WSEGOki;i+s + ki+s+1;j OPERACIJ.

pOSLE WY^ISLENIQ \TIH PROIZWEDENIJ NADO E]EPEREMNOVITX 2 MATRICY RAZMEROW mi;1 mi+s I mi+s mj . pOLU^AEMOB]EE ^ISLO OPERACIJ, STOQ]EE W ( ) W FIGURNYH SKOBKAH. tEPERXOSTAETSQ ZAMETITX, ^TO DLQ MINIMIZACII OB]EGO ^ISLA UMNOVENIJDOSTATO^NO PEREBOROM WYBRATX OPTIMALXNOE MESTO DLQ POSLEDNEJ OPERACII. uTWERVDENIE DOKAZANO.bUDEM RE[ATX PODZADA^I Bij QRUSAMI, OTNOSQ K QRUSU t WSE PODZADA^I S j ; i = t. rASSMOTRIM POSLEDOWATELXNO t = 0; 1; 2; : : : ; n ; 1.pRI t = 0 POLU^IM PODZADA^I Bij , DLQ KOTORYH kii = 0 I SKOBKI WOOB]ENE NADO RASSTAWLQTX. pRI RE[ENII O^EREDNOJ ZADA^I Bij S j ; i = tWOSPOLXZUEMSQ UTWERVDENIEM. pRI \TOM LEGKO WIDETX, ^TO SPRAWA W ( )BUDUT ISPOLXZOWATXSQ REZULXTATY PODZADA^ QRUSOW t1 < t, KOTORYE UVERE[ENY. tOGDA DLQ WY^ISLENIQ kij PO FORMULE ( ) DOSTATO^NO SDELATX2(j ; i) UMNOVENIJ, 2(j ; i) SLOVENIJ I j ; i ; 1 SRAWNENIJ.

oB]EE^ISLO OPERACIJ DLQ WY^ISLENIQ ODNOGO kij NE PREWOSHODIT O(n), A DLQWY^ISLENIQ WSEH kij | NE PREWOSHODIT O(n3) (POSKOLXKU OB]EE ^ISLOPODZADA^ Bij ESTX O(n2)). pRI WY^ISLENII kij UKAZANNYM SPOSOBOM MYNAHODIM I TO s, DLQ KOTOROGO DOSTIGAETSQ MINIMUM W ( ). eSLI MYDLQ WSEH (i; j ) BUDEM FIKSIROWATX \TO s, TO SMOVEM BYSTRO OPTIMALXNORASSTAWITX SKOBKI W ZADA^E B1n (W ISHODNOJ ZADA^E), RAZBIWAQ KAVDOEPROIZWEDENIE POSLEDOWATELXNO OPTIMALXNYM OBRAZOM NA 2 PROIZWEDENIQ. tEOREMA DOKAZANA.zADA^A O KRAT^AJ[IH PUTQH()-()..,,.10.pUSTX G |POLNYJ ORIENTIROWANNYJ GRAF S n WER[INAMIv1; v2; : : : ; vn : pUSTX KAVDOJ DUGE (vi ; vj ) SOPOSTAWLENO DEJSTWITELXNOE^ISLO dij > 0, LIBO dij = +1.

~ISLO dij TRAKTUETSQ KAK RASSTOQNIE IZ viW vj "NAPRQMU@". dLINA ORIENTIROWANNOGO PUTI IZ vi W vj OPREDELQETSQKAK SUMMA DLIN WSEH DUG \TOGO PUTI (ONA RAWNA +1, ESLI HOTQ BYODNO SLAGAEMOE RAWNO +1). kRAT^AJ[EE RASSTOQNIE dij IZ vi W vjOPREDELIM KAK MINIMUM DLIN PO WSEM ORIENTIROWANNYM PUTQM IZ vi Wvj . sOOTWETSTWU@]IJ PUTX BUDEM NAZYWATX KRAT^AJ[IM. rASSMOTRIMSLEDU@]U@ ZADA^U O KRAT^AJ[IH PUTQH.wHOD: MATRICA D = kdij k PORQDKA n (S^ITAEM, ^TO dii = 0 DLQ WSEHi).NIJ.tREBUETSQ: POSTROITX MATRICU D = kdij k KRAT^AJ[IH RASSTOQ-oTMETIM, ^TO ANALOGI^NU@ ZADA^U DLQ NEPOLNOGO GRAFA MOVNOSWESTI K ZADA^E O POLNOM GRAFE, POLOVIW dij = +1 DLQ NESU]ESTWU@]IH DUG. eSLI dij = dji DLQ WSEH i; j , TO GRAF G MOVNO S^ITATXNEORIENTIROWANNYM.aLGORITM DLQ UKAZANNOJ ZADA^I, OSNOWANNYJ NA PEREBORE WSEHWOZMOVNYH PUTEJ, IMEET NE MENEE, ^EM \KSPONENCIALXNU@ SLOVNOSTX,POSKOLXKU IZ vi W vj SU]ESTWUET BOLEE (n ; 2)! PUTEJ BEZ POWTORQ@]IHSQWER[IN.tEOREMA.

sU]ESTWUET ALGORITM DLQ ZADA^I O KRAT^AJ[IH PUTQH STROQ]IJ PO MATRICE D MATRICU D S ^ISLOM OPERACIJ ARIFMETI^ESKIH I SRAWNENIJ ^ISEL O(n3) GDE n ^ISLO WER[IN W GRAFEdOKAZATELXSTWO wWEDEM SLEDU@]IE (k)PODZADA^I: DLQ KAVDOJ PARY i; j I NATURALXNOGO k > 0 WY^ISLITX dij | MINIMALXNU@ DLINUSREDI WSEH ORIENTIROWANNYH PUTEJ IZ vi W vj , PROHODQ]IH, KROME vi Ivj , TOLXKO PO WER[INAM v1; v2; : : : ; vk (WOZMOVNO TOLXKO PO ^ASTI ILINAPRQMU@ IZ vi W vj ). eSLI k = 0, TO RAZRE[AETSQ TOLXKO PEREHOD IZ(0)(n)vi W vj "NAPRQMU@". pUSTX D(k) = kd(k)ij k. tOGDA D = D I D = D.bUDEM POSLEDOWATELXNO WY^ISLQTX D(1); D(2); : : : ; D(n).uTWERVDENIE.