В.Б. Алекссев - Сложные алгоритмы (1132790)
Текст из файла
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.
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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
