В.Б. Алексеев - Введение в теорию сложности алгоритмов (1158872), страница 2
Текст из файла (страница 2)
Ïîñêîëüêó â ïîëíîì áèíàðíîìäåðåâå âûñîòû h ÷èñëî ëèñòüåâ ðàâíî 2h , òî äëÿ ÷èñëà n ëèñòüåâ âèñõîäíîì äåðåâå âûïîëíÿåòñÿ íåðàâåíñòâî n 6 2h , èëè h > log2 n. Òàêêàê h íàòóðàëüíîå ÷èñëî, òî h > dlog2 ne.2) Îïÿòü äîñòðîèì äåðåâî d âûñîòû h äî ïîëíîãî áèíàðíîãî äåðåâà.Ïîñêîëüêó ê ëèñòó x ïîäêëåèâàåòñÿ ïîëíîå áèíàðíîå äåðåâî âûñîòûh − h(x), òî âìåñòî ëèñòà x îáðàçóåòñÿ 2h−h(x) ëèñòüåâ. Òàê êàê îáùåå÷èñëî ëèñòüåâ â ïîëíîì áèíàðíîì äåðåâå âûñîòû h ðàâíî 2h , òî ïîëó÷àåìP h−h(x)ðàâåíñòâî= 2h , ãäå ñóììèðîâàíèå âåäåòñÿ ïî âñåì ëèñòüÿìx2äåðåâà D.
Ñîêðàùàÿ íà 2h , ïîëó÷àåì ñëåäóþùåå ðàâåíñòâî, âåðíîå äëÿëþáîãî áèíàðíîãî äåðåâà:X 1= 1,h(x)2xãäå ñóììèðîâàíèå âåäåòñÿ ïî âñåì ëèñòüÿì äåðåâà D. Ïóñòü ÷èñëî ëèñòüåâ â äåðåâå D ðàâíî n. Ïî òåîðåìå î ñðåäíåì àðèôìåòè÷åñêîì èñðåäíåì ãåîìåòðè÷åñêîì n ïîëîæèòåëüíûõ ÷èñåë èìååì11X 1=>n n x 2h(x)snY 1=h(x)2x6r1n2Pxh(x).ÎòñþäàP2èxh(x)> nn .1Xh(x) > log2 n.n xËåììà äîêàçàíà.Òåïåðü óæå ëåãêî äîêàçàòü ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 1.2. Äëÿ ëþáîãî àëãîðèòìàìàññèâå èçnAïîèñêà â óïîðÿäî÷åííîìýëåìåíòîâ ñïðàâåäëèâû îöåíêèLñðA (n) > log2 n.LA (n) > dlog2 ne,Ïðåäñòàâèì àëãîðèòì A â âèäå áèíàðíîãî äåðåâàD. Òàê êàê ðåçóëüòàòîì àëãîðèòìà ìîæåò îêàçàòüñÿ ëþáîé íîìåð j îò1 äî n (òàêîé, ÷òî aj = a), òî â äåðåâå D íå ìåíåå n ëèñòüåâ. Ïîýòîìóñðóòâåðæäåíèå òåîðåìû ñëåäóåò èç îïðåäåëåíèÿ âåëè÷èí LA (n) è LA (n) èëåììû.Äîêàçàòåëüñòâî.1.2.
Ñîðòèðîâêà êà÷åñòâå åùå îäíîãî ïðèìåðà ðàññìîòðèì çàäà÷ó ñîðòèðîâêè íàëèíåéíî óïîðÿäî÷åííîì ìíîæåñòâå, êîòîðàÿ îáû÷íî ñòàâèòñÿ ñëåäóþùèì îáðàçîì.Âõîä: ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ a1 , a2 , . . . , an íåêîòîðîãî ëèíåéíî óïîðÿäî÷åííîãî ìíîæåñòâà (äëÿ ïðîñòîòû áóäåì ñ÷èòàòü, ÷òîai 6= aj ïðè i 6= j ).Âûõîä: ïåðåñòàíîâêà (i1 , i2 , . .
. , in ) ýëåìåíòîâ 1, 2, . . . , n òàêàÿ, ÷òîai1 < ai2 < . . . < ain .Îäèí øàã àëãîðèòìà: ñðàâíåíèå ëþáîé ïàðû ýëåìåíòîâ ai è aj èëþáîå èñïîëüçîâàíèå ïîëó÷åííîãî îòâåòà ai < aj èëè ai > aj . Àëãîðèòì ñ÷èòàåì äåòåðìèíèðîâàííûì, òî åñòü äëÿ äàííîãî n îäíîçíà÷íîîïðåäåëåíà ïàðà íîìåðîâ (i, j) òåõ ýëåìåíòîâ, êîòîðûå ñðàâíèâàþòñÿíà ïåðâîì øàãå.  çàâèñèìîñòè îò îäíîãî èç äâóõ îòâåòîâ îäíîçíà÷íîîïðåäåëÿåòñÿ ïàðà íîìåðîâ òåõ ýëåìåíòîâ, êîòîðûå ñðàâíèâàþòñÿ íàâòîðîì øàãå è ò.ä.
Òàêèì îáðàçîì, àëãîðèòì ìîæíî ïðåäñòàâèòü â âèäåáèíàðíîãî êîðíåâîãî äåðåâà, â êîòîðîì êàæäîé âåðøèíå, îòëè÷íîé îòëèñòüåâ, ïðèïèñàíà ïàðà íîìåðîâ ñðàâíèâàåìûõ ýëåìåíòîâ, à ëèñòüÿìïðèïèñàíû îòâåòû â âèäå ïåðåñòàíîâîê (i1 , i2 , . . . , in ).Îïðåäåëåíèå. Ñëîæíîñòüþ LA (n) àëãîðèòìà ñîðòèðîâêè A íàçûâàåòñÿ ìàêñèìàëüíîå ÷èñëî âîïðîñîâ îò íà÷àëà ðàáîòû äî îòâåòà, ãäå7ìàêñèìóì áåðåòñÿ ïî âñåì âîçìîæíûì âõîäíûì ïîñëåäîâàòåëüíîñòÿìäëèíû n.
Ñëîæíîñòüþ ñîðòèðîâêè n ýëåìåíòîâ Lñîðò (n) íàçûâàåòñÿmin LA (n), ãäå ìèíèìóì áåðåòñÿ ïî âñåì àëãîðèòìàì, ñîðòèðóþùèìïðàâèëüíî n ýëåìåíòîâ.Òåîðåìà 1.3. Äëÿ ëþáîãî àëãîðèòìàA, ñîðòèðóþùåãî n ýëåìåíòîâ, âûïîëíÿåòñÿ íåðàâåíñòâî LA (n) > log2 n!.Äîêàçàòåëüñòâî. Àëãîðèòì A ìîæíî ïðåäñòàâèòü â âèäå áèíàðíîãî äåðåâà D. Ëþáàÿ ïåðåñòàíîâêà (i1 , i2 , .
. . , in ) ýëåìåíòîâ 1, 2, . . . , nìîæåò áûòü îòâåòîì â àëãîðèòìå è, ñëåäîâàòåëüíî, äîëæíà áûòü ïðèïèñàíà õîòÿ áû îäíîìó ëèñòó. Ïîýòîìó â äåðåâå D íå ìåíåå n! ëèñòüåâ.Îòñþäà ïî ëåììå 1.1 ïîëó÷àåì, ÷òî âûñîòà äåðåâà h(D) > log2 n!. Íî, ïîîïðåäåëåíèþ LA (n) = h(D). Òåîðåìà äîêàçàíà.Ñëåäñòâèå 1. Lñîðò (n) > log2 n!.Èñïîëüçóÿ ôîðìóëó Ñòèðëèíãà äëÿ n!, ïîëó÷àåìÑëåäñòâèå 2. Lñîðò (n) > (1 − o(1))n log2 n (èëè Lñîðò (n) &n log2 n).Ðàññìîòðèì äàëåå 2 àëãîðèòìà ñîðòèðîâêè, ñëîæíîñòü êîòîðûõáëèçêà ê ïîëó÷åííîé íèæíåé îöåíêå.Ñîðòèðîâêà âñòàâêàìèÏîñëåäîâàòåëüíî ðåøàåì ïîäçàäà÷è: îòñîðòèðîâàòü a1 , .
. . , ak ïðèk = 1, 2, . . . , n. Ïðè k = 1 (áàçèñ) îòâåò òðèâèàëåí, ïðè k = n ïîëó÷àåì îòâåò âñåé çàäà÷è. Ïåðåõîä îò ïîäçàäà÷è ñ ïàðàìåòðîì k − 1 êk ïðîèñõîäèò ïóòåì âñòàâêè â óæå óïîðÿäî÷åííóþ ïîñëåäîâàòåëüíîñòüai1 < ai2 < . . . < aik−1 ýëåìåíòà ak íà ñîîòâåòñòâóþùåå ìåñòî. Ïðèýòîì äëÿ ak èìååòñÿ k âîçìîæíûõ ïîëîæåíèé: ïåðåä ai1 , ìåæäó ai1 èai2 ,.
. ., ïîñëå aik−1 . Âñòàâêà ak íà íóæíîå ìåñòî îñóùåñòâëÿåòñÿ áèíàðíûìïîèñêîì.Òåîðåìà 1.4. Ñëîæíîñòü àëãîðèòìà ñîðòèðîâêè âñòàâêàìèLâñò (n) 6 log2 n! + n − 1.Äîêàçàòåëüñòâî. Òàê êàê ïðè âñòàâêå ýëåìåíòà ak âíà÷àëå èìååòñÿk âîçìîæíûõ ïîëîæåíèé: ïåðåä ai1 , ìåæäó ai1 è ai2 , . . .
, ïîñëå aik−1 , òî äëÿâñòàâêè ak áèíàðíûì ïîèñêîì íóæíî ñäåëàòü íå áîëåå dlog2 ke ñðàâíåíèé.Âåñü àëãîðèòì òðåáóåò ñðàâíåíèé íå áîëåå dlog2 2e + dlog2 3e + dlog2 4e +. . . + dlog2 ne 6 log2 2 + log2 3 + . . . + log2 n + (n − 1) = log2 n! + n − 1.Ñëåäñòâèå 3. Lâñò (n) 6 (1 + o(1))n log2 n ïðè n → ∞.Ñëåäñòâèå 4.
Lñîðò (n) ∼ n log2 n ïðè n → ∞.Ïîñëåäíåå ñëåäñòâèå âûòåêàåò èç ñëåäñòâèé 2 è 3.Lâñò (n)óäîâëåòâîðÿåò íåðàâåíñòâóÑîðòèðîâêà ñëèÿíèåì8Ñîðòèðîâêà ñëèÿíèåì n ýëåìåíòîâ îïèñûâàåòñÿ ðåêóðñèâíî. Åñëèn = 1, òî çàäà÷à òðèâèàëüíà. Äëÿ n > 2 äåëèì ïîñëåäîâàòåëüíîñòüa1 , a2 , . . . , an íà 2 ïîñëåäîâàòåëüíîñòè a1 , a2 , . . .
, ab n2 c è ab n2 c+1 , . . . , an ,ñîðòèðóåì òåì æå àëãîðèòìîì ñîðòèðîâêè ñëèÿíèåì êàæäóþ èç ïîäïîñëåäîâàòåëüíîñòåé è çàòåì ñëèâàåì 2 ïîëó÷åííûå îòñîðòèðîâàííûåïîñëåäîâàòåëüíîñòè A = (ai1 < ai2 < . . . < aib n2 c ) è B = (aj1 <aj2 < . . . < ajn−b n c ), ôîðìèðóÿ îòñîðòèðîâàííóþ ïîñëåäîâàòåëüíîñòü2C . Íà êàæäîì øàãå ñëèÿíèÿ ìû ñðàâíèâàåì ïåðâûå ýëåìåíòû èç Aè B è ïåðåíîñèì ìåíüøèé èç íèõ î÷åðåäíûì ýëåìåíòîì â C (åñëèA èëè B ñòàíîâèòñÿ ïóñòûì, òî ïåðåíîñèì îñòàâøèåñÿ ýëåìåíòû â Cïî ïîðÿäêó).
Ïóñòü Lñë (n) ñëîæíîñòü (÷èñëî ñðàâíåíèé) àëãîðèòìàñîðòèðîâêè ñëèÿíèåì äëÿ n ýëåìåíòîâ â õóäøåì ñëó÷àå. Òîãäà Lñë (1) = 0è Lñë (n) = Lñë (b n2 c) + Lñë (d n2 e) + n − 1 ïðè n > 2, ïîñêîëüêó íà ñëèÿíèåâ õóäøåì ñëó÷àå ìîæåò ïîòðåáîâàòüñÿ n − 1 ñðàâíåíèé.Lñë (n) = n log2 n − n + 1 äëÿ n = 2k , ãäå k - ëþáîåíàòóðàëüíîå ÷èñëî èëè k = 0.Äîêàçàòåëüñòâî (èíäóêöèåé ïî k ).
Ïðè k = 0 ïîëó÷àåì âåðíîåðàâåíñòâî Lñë (1) = 0. Ïóñòü óòâåðæäåíèå ëåììû âåðíî ïðè âñåõ 0 6k 6 m − 1, ãäå m - íàòóðàëüíîå ÷èñëî. Òîãäà äëÿ k = m èìååì Lñë (2m ) =2Lñë (2m−1 ) + 2m − 1 = 2(2m−1 · (m − 1) − 2m−1 + 1) + 2m − 1 = m2m − 2m + 1,òî åñòü äëÿ k = m óòâåðæäåíèå ëåììû òàêæå âåðíî.
Ñëåäîâàòåëüíî, îíîâåðíî äëÿ âñåõ íàòóðàëüíûõ k .Òåîðåìà 1.5. Lñë (n) < 2n log2 n + 1 äëÿ âñåõ íàòóðàëüíûõ n.Äîêàçàòåëüñòâî. Óòâåðæäåíèå òåîðåìû ñïðàâåäëèâî ïðè n = 1.Äëÿ ëþáîãî íàòóðàëüíîãî n > 2 íàéäåòñÿ íàòóðàëüíîå k òàêîå, ÷òî2k−1 < n 6 2k . Ôóíêöèÿ Lñë (n), î÷åâèäíî, íå óáûâàåò ñ ðîñòîì n.Ïîýòîìó Lñë (n) 6 Lñë (2k ) = 2k · k − 2k + 1 = 2k (k − 1) + 1 < 2n log2 n + 1.Òåîðåìà äîêàçàíà.Ëåììà 1.2.92.
Ðåêóððåíòíûå ìåòîäû ïîñòðîåíèÿ àëãîðèòìîâ.Îäíî èç âàæíûõ íàïðàâëåíèé â ïîñòðîåíèè áûñòðûõ àëãîðèòìîâ ýòî ðåêóððåíòíûå ìåòîäû. Ïðè ýòîì ðåøåíèå çàäà÷è ñâîäèòñÿ ê ðåøåíèþ áîëåå ïðîñòûõ ïîäçàäà÷ òàêîãî æå òèïà, êîòîðûå, â ñâîþ î÷åðåäü,ñâîäÿòñÿ ê åùå áîëåå ïðîñòûì ïîäçàäà÷àì è ò.ä. Åñòåñòâåííî ïðè ýòîìäîëæåí áûòü íåêîòîðûé áàçèñíûé óðîâåíü, çàäà÷è êîòîðîãî ðåøàþòñÿóæå íå ðåêóððåíòíî, à íåïîñðåäñòâåííî. Ìîæíî âûäåëèòü 2 îñíîâíûõðåêóððåíòíûõ ìåòîäà, êîòîðûå èñïîëüçóþòñÿ äëÿ ïîñòðîåíèÿ áûñòðûõàëãîðèòìîâ: ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ è ìåòîä ðàçäåëÿéè âëàñòâóé.2.1.
Ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ñàìîì øèðîêîì âèäå èäåÿ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿñîñòîèò â âûäåëåíèè â äàííîé çàäà÷å ñ ïàðàìåòðîì n (õàðàêòåðèçóþùèìäëèíó âõîäà) ïîäçàäà÷ ñ ìåíüøèìè ïàðàìåòðàìè è ðåøåíèè ïîäçàäà÷â ñîîòâåòñòâèè ñ óâåëè÷åíèåì ïàðàìåòðà, íà÷èíàÿ ñ ñàìîãî ìåíüøåãî(îáû÷íî 0 èëè 1). Ïðè ýòîì çàäà÷à ñ ïàðàìåòðîì k ðåøàåòñÿ, êîãäà óæåðåøåíû âñå ïîäçàäà÷è ñ ïàðàìåòðîì k − 1 è ìåíüøå (èíîãäà íå k − 1,à k − c, ãäå c êîíñòàíòà). Ïðè ýòîì áîëüøîãî ÷èñëà ïîäçàäà÷ óäàåòñÿ÷àñòî èçáåæàòü çà ñ÷åò òîãî, ÷òî ðåøåíèå ðàçíûõ ïîäçàäà÷ ñâîäèòñÿ êðåøåíèþ îäíèõ è òåõ æå ïîäçàäà÷.
Ðàññìîòðèì ïðèìåðû.Çàäà÷à îá îïòèìàëüíîì ïîðÿäêå óìíîæåíèÿ ìàòðèö.Ìû áóäåì ðàññìàòðèâàòü çäåñü òîëüêî îáû÷íûé ñïîñîá óìíîæåíèÿäâóõ ìàòðèö (ñòðî÷êà íà ñòîëáåö) è áóäåì ó÷èòûâàòü òîëüêî ÷èñëîóìíîæåíèé ýëåìåíòîâ. Ïðè ýòîì åñëè ìàòðèöû A è B èìåþò ðàçìåðûm×n è n×p, òî äëÿ âû÷èñëåíèÿ A·B òðåáóåòñÿ, î÷åâèäíî, mnp óìíîæåíèé ýëåìåíòîâ. Èçâåñòíî, ÷òî äëÿ ëþáûõ òðåõ ìàòðèö (AB)C = A(BC),òî åñòü ïðîèçâåäåíèå ìàòðèö íå çàâèñèò îò ðàññòàíîâêè ñêîáîê.
Îäíàêî÷èñëî îïåðàöèé óìíîæåíèÿ ýëåìåíòîâ ìîæåò ïðè ýòîì îêàçàòüñÿ ðàçíûì.Ïðèìåð. Ïóñòü ìàòðèöû A, B, C èìåþò ðàçìåðû n×1, 1×n, n×n.Òîãäà ìàòðèöà AB èìååò ðàçìåðû n × n è ïðè âû÷èñëåíèè (AB)Cèñïîëüçóåòñÿ n2 + n3 óìíîæåíèé ýëåìåíòîâ. Ìàòðèöà BC èìååò ðàçìåðû1 × n, ïîýòîìó ïðè âû÷èñëåíèè A(BC) èñïîëüçóåòñÿ n2 + n2 = 2n2óìíîæåíèé ýëåìåíòîâ, ÷òî ïðèìåðíî â n2 ðàç ìåíüøå, ÷åì äëÿ (AB)C .Òàêèì îáðàçîì, èìååò ñìûñë ñëåäóþùàÿ çàäà÷à.Çàäà÷à.
Âõîä: íàáîð íàòóðàëüíûõ ÷èñåë (m0 , m1 , . . . , mn ) (êîòîðûé çàäàåò ðàçìåðû ìàòðèö â ïðîèçâåäåíèè A1 A2 · . . . · An , ãäå Ai èìååòðàçìåðû mi−1 × mi ).10ðàññòàâèòü ñêîáêè â ïðîèçâåäåíèè A1 · A2 · . . . · Anòàê, ÷òîáû îáùåå ÷èñëî óìíîæåíèé ýëåìåíòîâ áûëî ìèíèìàëüíûì, èâû÷èñëèòü ýòî ìèíèìàëüíîå ÷èñëî.Ïîñìîòðèì ñíà÷àëà, êàêîâà ñëîæíîñòü òðèâèàëüíîãî àëãîðèòìà,êîòîðûé ïåðåáèðàåò âñå ñïîñîáû ðàññòàíîâêè ñêîáîê. Ïóñòü an ÷èñëîñïîñîáîâ ïðàâèëüíîé ðàññòàíîâêè ñêîáîê â ïðîèçâåäåíèè A1 · A2 · .
. . · An .Òðåáóåòñÿ:Òåîðåìà 2.1.n−1an = n1 C2n−2=(2n−2)!n!(n−1)! ïðèn > 2.Î÷åâèäíî, ÷òî a1 = 1, a2 = 1, a3 = 2. Îïåðàöèÿ,êîòîðóþ ìû ñäåëàåì ïîñëåäíåé â A1 · A2 · . . . · An , ñâîäèò çàäà÷ó ê 2ïîäçàäà÷àì A1 · . . . · Ak è Ak+1 · . . . · An , ãäå 1 6 k 6 n − 1. Ïîýòîìó ïðèÄîêàçàòåëüñòâî.n>2an = a1 an−1 + a2 an−2 + . . . + an−1 a1 .Ðàññìîòðèì ïðîèçâîäÿùóþ ôóíêöèþf (x) = a1 x + a2 x2 + a3 x3 + . .
. + an xn + . . .(2.1)Òîãäàf 2 (x) = (a1 a1 )x2 + (a1 a2 + a2 a1 )x3 + (a1 a3 + a2 a2 + a3 a1 )x4 + . . . =a2 x2 + a3 x3 + a4 x4 + . . . = f (x) − a1 x = f (x) − x.Òàêèì îáðàçîì, f 2 (x)− f (x) + x = 0. Ðåøàÿ êâàäðàòíîå √óðàâíåíèå,√. Ïîñêîëüêó f (0) = 0, òî f (x) = 1− 1−4x. Ðàñïîëó÷àåì f (x) = 1± 1−4x22êëàäûâàÿ f (x) â ðÿä Òåéëîðà è ñðàâíèâàÿ ñ (2.1), ïîëó÷àåì (ïðîâåðüòå):2n − 3 4n−11 3 5an = · · · . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
