В.Б. Алекссев - Сложные алгоритмы (1132790), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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 .

Характеристики

Список файлов книги