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

wWEDENIEkAVDYJ ALGORITM A HARAKTERIZUETSQ TEM, ^TO NA EGO WHOD MOGUTPOSTUPATX RAZLI^NYE WHODNYE DANNYE x, KOTORYE ON PREOBRAZUET WNEKOTORYE WYHODNYE DANNYE y. pRI \TOM PROCESS RABOTY A NA WHODNYHDANNYH x MOVNO OHARAKTERIZOWATX NEKOTORYMI SLOVNOSTNYMI HARAKTERISTIKAMI LA(x) (^ISLO [AGOW ALGORITMA, OB_EM ISPOLXZUEMOJ PAMQTI I DR.). oDNAKO DATX QWNOE PREDSTAWLENIE FUNKCII LA (x) DLQ WSEHx OBY^NO NE PREDSTAWLQETSQ WOZMOVNYM.

dAVE POWEDENIE LA(x) KAKFUNKCII OT x OBY^NO TRUDNO OPISATX. pO\TOMU PRI ANALIZE SLOVNOSTIALGORITMOW ^ASTO RASSMATRIWA@T BOLEE GRUBYE HARAKTERISTIKI. nAIBOLEE RASPROSTRANENNYM QWLQETSQ SLEDU@]IJ PODHOD. wHODNYE DANNYEHARAKTERIZU@TSQ NEKOTORYM NATURALXNYM PARAMETROM n IH SLOVNOSTI (^A]E WSEGO n | DLINA PREDSTAWLENIQ WHODNYH DANNYH NEKOTORYMZADANNYM SPOSOBOM).

dALEE IZU^AETSQ FUNKCIQ LA(n), OPREDELQEMAQKAK MAKSIMUM LA(x) PO WSEM x S PARAMETROM n (SLOVNOSTX W HUD[EMSLU^AE) ILI KAK NEKOTOROE SREDNEE LA (x) PO WSEM x S PARAMETROM n(SREDNQQ SLOVNOSTX). w \TIH SLU^AQH UVE UDAETSQ POLU^ATX INTERESNYEREZULXTATY. w DANNOM POSOBII MY BUDEM RASSMATRIWATX TOLXKO ODNUSLOVNOSTNU@ HARAKTERISTIKU ALGORITMOW | WREMQ, ILI ^ISLO [AGOW,RABOTY ALGORITMA.

pRI \TOM MY DOLVNY ^ETKO OPREDELQTX, ^TO TAKOE[AG ALGORITMA. eSLI VE MY HOTIM POLU^ATX UTWERVDENIQ TIPA "DLQL@BOGO ALGORITMA", TO MY TAKVE DOLVNY ^ETKO OPISATX WESX KLASSALGORITMOW, KOTORYE MY RASSMATRIWAEM. mY POQSNIM \TO WNA^ALEPRIMERAMI.pOISK W UPORQDO^ENNOM MASSIWE.pUSTX IMEETSQ UPORQDO^ENNYJ MASSIW \LEMENTOW IZ NEKOTOROGOLINEJNO UPORQDO^ENNOGO MNOVESTWA a1 < a2 < : : : < an. nA WHOD ALGORITMA BUDET POSTUPATX NEKOTORYJ \LEMENT a, SOWPADA@]IJ S ODNIM IZ\LEMENTOW a1; a2; : : : ; an. oDIN [AG ALGORITMA SOSTOIT W SRAWNENII a cNEKOTORYM ai, POLU^ENII ODNOGO IZ DWUH OTWETOW a 6 ai ILI a > ai IANALIZE \TOGO OTWETA.

aLGORITM DOLVEN WYDATX NOMER j TOGO \LEMENTAaj , DLQ KOTOROGO a = aj . rASSMOTRIM, NAPRIMER, ALGORITM, KOTORYJSRAWNIWAET a PO O^EREDI SO WSEMI \LEMENTAMI OT a1 DO an. tOGDA ESLIa = a1, ON MOVET WYDATX OTWET UVE POSLE 1-GO [AGA. oDNAKO, ESLIa = an;1 ILI a = an, TO ALGORITM BUDET DELATX n ; 1 [AGOW. w SREDNEM,ESLI S^ITATX, ^TO a SOWPADAET S L@BYM ai c WEROQTNOSTX@ n1 , ^ISLO1[AGOW BUDET (1+2+:::+nn ;1)+n;1 = n+12 ; n.1w DALXNEJ[EM MY BUDEM ALGORITMY S^ITATX DETERMINIROWANNYMI. tAK, NAPRIMER, DLQ L@BOGO ALGORITMA POISKA \LEMENTA W UPORQDO^ENNOM MASSIWE NA PERWOM [AGE ODNOZNA^NO OPREDELQETSQ NOMER i\LEMENTA, S KOTORYM SRAWNIWAETSQ a.

|TOT NOMER NE ZAWISIT OT WHODA a.w ZAWISIMOSTI OT OTWETA (a 6 ai ILI a > ai) ODNOZNA^NO OPREDELQETSQSLEDU@]IJ NOMER \LEMENTA, S KOTORYM SRAWNIWAETSQ a, I T.D. tAKIMOBRAZOM WSQKIJ ALGORITM POISKA (IZ UKAZANNOGO WY[E KLASSA) MOVNOPREDSTAWITX KORNEWYM BINARNYM DEREWOM, W KOTOROM KAVDOJ WER[INE,OTLI^NOJ OT LISTXEW, PRIPISAN NEKOTORYJ NOMER \LEMENTA S KOTORYMSRAWNIWAETSQ a, A KAVDOMU LISTU PRIPISAN NOMER \LEMENTA, RAWNOGO a.oPREDELENIE. sLOVNOSTX@ W HUD[EM SLU^AE LA(n) ALGORITMA POISKA W UPORQDO^ENNOM MASSIWE IZ n \LEMENTOW NAZYWAETSQMAKSIMALXNOE ^ISLO SRAWNENIJ \LEMENTA a SSR\LEMENTAMI MASSIWA DOPOLU^ENIQ OTWETA sREDNEJ SLOVNOSTX@ LA (n) ALGORITMA POISKAA W UPORQDO^ENNOMMASSIWE IZ n \LEMENTOW NAZYWAETSQ WELI^INAPnSR1LA (n) = n i=1LA(ai) GDE LA(ai) ^ISLO [AGOW ALGORITMA ESLI WHOD()-.a = ai,|,.eSLI - DEJSTWITELXNOE ^ISLO, TO ^EREZ bc I de MY BUDEMOBOZNA^ATX NAIBOLX[EE (SOOTWETSTWENNO, NAIMENX[EE) CELOE ^ISLO, NEBOLX[EE (SOOTWETSTWENNO, NE MENX[EE) ^EM .

~ASTO bc OBOZNA^A@T[] I NAZYWA@T CELOJ ^ASTX@ ^ISLA .tEOREMA. sU]ESTWUET ALGORITM A POISKA W UPORQDO^ENNOMMASSIWE DLQ KOTOROGO LA(n) = blog2 ncdOKAZATELXSTWO dOKAZYWATX SU]ESTWOWANIE ALGORITMA S NUVNYMI SWOJSTWAMI OBY^NO LEGKO | DOSTATO^NO QWNO PRED_QWITX TAKOJALGORITM. tREBUEMOMU W TEOREME USLOWI@ UDOWLETWORQET SLEDU@]IJALGORITM, NAZYWAEMYJ "BINARNYM POISKOM", I OPISYWAEMYJ REKURRENTNO.eSLI n = 1, TO WYDATX OTWET a = a1.eSLI n > 2, TO WY^ISLITX k = b n2 c I SRAWNITX a S ak .

eSLI a 6 ak,TO REKURRENTNO (TEM VE ALGORITMAM) OSU]ESTWITX POISK a W MASSIWEa1 < a2 < : : : < ak. eSLI a > ak , TO OSU]ESTWITX (REKURRENTNO) POISK aW MASSIWE ak+1 < ak+2 < : : : < an.w L@BOM SLU^AE DLINA POLU^AEMOGO MASSIWA NE PREWOSHODIT n ;nb 2 c = d n2 e, I, SLEDOWATELXNO, LA(n) = 1+LA(d n2 e). kROME TOGO LA(1) = 0.dOKAVEM INDUKCIEJ PO m, ^TO DLQ WSEH NATURALXNYH n, TAKIH, ^TO2m;1 < n 6 2m , WYPOLNQETSQ LA(n) = m. pRI m = 0 POLU^AEM n = 1 ILA(1) = 0 = m. pUSTX UTWERVDENIE WERNO DLQ m = p I 2p < n 6 2p+1.tOGDA 2p;1 < d n2 e 6 2p I PO PREDPOLOVENI@ INDUKCII LA(d n2 e) = p.,..2oTS@DA LA (n) = 1 + LA(d n2 e) = p + 1, TO ESTX UTWERVDENIE WERNO DLQm = p + 1.

pO INDUKCII POLU^AEM, ^TO UTWERVDENIE WERNO DLQ WSEH n,TO ESTX LA(n) = m = dlog2 ne. tEOREMA DOKAZANA.sLEDSTWIE. dLQ ALGORITMA A BINARNOGO POISKA LSRA (n) 6dlog2 nedOKAZATX UTWERVDENIE TIPA "DLQ L@BOGO ALGORITMA" OBY^NO SU]ESTWENNO TRUDNEE, ^EM UTWERVDENIE TIPA "SU]ESTWUET ALGORITM". w\TOM SLU^AE MY DOLVNY ^ETKO OPISATX WESX KLASS RASSMATRIWAEMYHALGORITMOW. wY[E BYLO UKAZANO, ^TO L@BOJ ALGORITM POISKA W UPORQDO^ENNOM MASSIWE IZ n \LEMENTOW MOVNO PREDSTAWITX W WIDE BINARNOGODEREWA.

pO\TOMU DALEE MY RASSMOTRIM NEKOTORYE SWOJSTWA BINARNYHDEREWXEW.oPREDELENIE. gLUBINOJ h(x) LISTA x W KORNEWOM DEREWE D BUDEM NAZYWATX ^ISLO REBER W EDINSTWENNOM PUTI IZ KORNQ DEREWA WLIST x wYSOTOJ h(D) DEREWA D BUDEM NAZYWATX max h(x) GDE MAKSIMUM BERETSQ PO WSEM LISTXQM DEREWA D sREDNEJ WYSOTOJ hSR(D)DEREWA D BUDEM NAZYWATX SREDNEE ARIFMETI^ESKOE WELI^IN h(X ) POWSEM LISTXQM DEREWA DlEMMA. dLQ L@BOGO BINARNOGO DEREWA S n LISTXQMI WYPOLNQ@TSQ NERAWENSTWA h(D) > dlog2 ne hSR(D) > log2 ndOKAZATELXSTWO 1)l@BOE BINARNOE DEREWO WYSOTY h MOVNO DOSTROITX DO POLNOGO BINARNOGO DEREWA WYSOTY h (W KOTOROM WSE PUTIOT KORNQ DO LISTXEW SODERVAT PO h REBER). dLQ \TOGO DOSTATO^NOK KAVDOMU LISTU x WYSOTY h(x) PODKLEITX POLNOE BINARNOE DEREWOWYSOTY h ; h(x).

pRI \TOM ^ISLO LISTXEW NE UMENX[ITSQ. pOSKOLXKUW POLNOM BINARNOM DEREWE WYSOTY h ^ISLO LISTXEW RAWNO 2h , TO DLQ^ISLA n LISTXEW W ISHODNOM DEREWE WYPOLNQETSQ NERAWENSTWO n 6 2h,ILI h > log2 n. tAK KAK h | NATURALXNOE ^ISLO, TO h > dlog2 ne.2)oPQTX DOSTROIM DEREWO d WYSOTY h DO POLNOGO BINARNOGO DEREWA. pOSKOLXKU K LISTU x PODKLEIWAETSQ POLNOE BINARNOE DEREWO WYSOTYh ; h(x), TO WMESTO LISTA x OBRAZUETSQ 2h;h(x) LISTXEW.

tAK KAK OB]EE^ISLO LISTXEW W POLNOMBINARNOM DEREWE WYSOTY h RAWNO 2h, TO POPLU^AEM RAWENSTWO x 2h;h(x) = 2h GDE SUMMIROWANIE WEDETSQ PO WSEMLISTXQM DEREWA D. sOKRA]AQ NA 2h, POLU^AEM SLEDU@]EE RAWENSTWO,WERNOE DLQ L@BOGO BINARNOGO DEREWA:.-().,-..-: 1), 2)..Xx12h(x)= 1; ()GDE SUMMIROWANIE WEDETSQ PO WSEM LISTXQM DEREWA D. pUSTX ^ISLOLISTXEW W DEREWE D RAWNO n. pO TEOREME O SREDNEM ARIFMETI^ESKOM I3SREDNEM GEOMETRI^ESKOM n POLOVITELXNYH ^ISEL IMEEM1 1X 1n = n x 2h(x) >sYnx1=2h(x)rn2Px1h(x) :oTS@DAP2 x h(x) > nn.IP1n x h(x) > log2 n.lEMMA DOKAZANA.tEPERX UVE LEGKO DOKAZATX SLEDU@]EE UTWERVDENIE.tEOREMA. dLQ L@BOGO ALGORITMA A POISKA W UPORQDO^ENNOMMASSIWE IZ n \LEMENTOW SPRAWEDLIWY OCENKILA(n) > dlog ne; LSR(n) > log n:2A2dOKAZATELXSTWO pREDSTAWIM ALGORITM A W WIDE BINARNOGO DEREWA D.

tAK KAK REZULXTATOM ALGORITMA MOVET OKAZATXSQ L@BOJ NOMERj OT 1 DO n (TAKOJ, ^TO aj = a), TO W DEREWE D NE MENEE n LISTXEW.pO\TOMUUTWERVDENIE TEOREMY SLEDUET IZ OPREDELENIQ WELI^IN LA(n)SRI L (n) I LEMMY..A4sORTIROWKAw KA^ESTWE E]E ODNOGO PRIMERA RASSMOTRIM ZADA^U SORTIROWKINA LINEJNO UPORQDO^ENNOM MNOVESTWE, KOTORAQ OBY^NO STAWITSQ SLEDU@]IM OBRAZOM.wHOD: POSLEDOWATELXNOSTX \LEMENTOW a1; a2; : : : ; an NEKOTOROGO LINEJNO UPORQDO^ENNOGO MNOVESTWA (DLQ PROSTOTY BUDEM S^ITATX, ^TOai =6 aj PRI i =6 j ).wYHOD: PERESTANOWKA (i1; i2; : : : ; in) \LEMENTOW 1; 2; : : : ; n TAKAQ,^TO ai1 < ai2 < : : : < ain .oDIN [AG ALGORITMA: SRAWNENIE L@BOJ PARY \LEMENTOW ai I aj IL@BOE ISPOLXZOWANIE POLU^ENNOGO OTWETA ai < aj ILI ai > aj . aLGORITM S^ITAEM DETERMINIROWANNYM, TO ESTX DLQ DANNOGO n ODNOZNA^NOOPREDELENA PARA NOMEROW (i; j ) TEH \LEMENTOW, KOTORYE SRAWNIWA@TSQNA PERWOM [AGE. w ZAWISIMOSTI OT ODNOGO IZ DWUH OTWETOW ODNOZNA^NOOPREDELQETSQ PARA NOMEROW TEH \LEMENTOW, KOTORYE SRAWNIWA@TSQ NAWTOROM [AGE I T.D.