В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 2
Текст из файла (страница 2)
×àñòî bαc îáîçíà÷àþò [α]è íàçûâàþò öåëîé ÷àñòüþ ÷èñëà α.Òåîðåìà 1.1. Ñóùåñòâóåò àëãîðèòìAïîèñêà â óïîðÿäî÷åííîìLA (n) = dlog2 ne.Äîêàçàòåëüñòâî. Äîêàçûâàòü ñóùåñòâîâàíèå àëãîðèòìà ñ íóæíûìè ñâîéñòâàìè îáû÷íî ëåãêî äîñòàòî÷íî ÿâíî ïðåäúÿâèòü òàêîé àëãîðèòì. Òðåáóåìîìó â òåîðåìå óñëîâèþ óäîâëåòâîðÿåò ñëåäóþùèé àëãîðèòì, íàçûâàåìûé áèíàðíûì ïîèñêîì, è îïèñûâàåìûé ðåêóððåíòíî.Åñëè n = 1, òî âûäàòü îòâåò a = a1 .Åñëè n > 2, òî âû÷èñëèòü k = b n2 c è ñðàâíèòü a ñ ak .
Åñëè a 6 ak ,òî ðåêóððåíòíî (òåì æå àëãîðèòìàì) îñóùåñòâèòü ïîèñê a â ìàññèâåa1 < a2 < . . . < ak . Åñëè a > ak , òî îñóùåñòâèòü (ðåêóððåíòíî) ïîèñê aâ ìàññèâå ak+1 < ak+2 < . . . < an . ëþáîì ñëó÷àå äëèíà ïîëó÷àåìîãî ìàññèâà íå ïðåâîñõîäèò n −nb 2 c = d n2 e, è, ñëåäîâàòåëüíî, LA (n) = 1 + LA (d n2 e). Êðîìå òîãî LA (1) =0. Äîêàæåì èíäóêöèåé ïî m, ÷òî äëÿ âñåõ íàòóðàëüíûõ n, òàêèõ, ÷òî2m−1 < n 6 2m , âûïîëíÿåòñÿ LA (n) = m. Ïðè m = 0 ïîëó÷àåì n = 1 èLA (1) = 0 = m. Ïóñòü óòâåðæäåíèå âåðíî äëÿ m = p è 2p < n 6 2p+1 .Òîãäà 2p−1 < d n2 e 6 2p è ïî ïðåäïîëîæåíèþ èíäóêöèè LA (d n2 e) = p.Îòñþäà LA (n) = 1 + LA (d n2 e) = p + 1, òî åñòü óòâåðæäåíèå âåðíî äëÿm = p + 1.
Ïî èíäóêöèè ïîëó÷àåì, ÷òî óòâåðæäåíèå âåðíî äëÿ âñåõ n,òî åñòü LA (n) = m = dlog2 ne. Òåîðåìà äîêàçàíà.ñðÑëåäñòâèå. Äëÿ àëãîðèòìà A áèíàðíîãî ïîèñêà LA (n) 6ìàññèâå, äëÿ êîòîðîãî5dlog2 ne.Äîêàçàòü óòâåðæäåíèå òèïà äëÿ ëþáîãî àëãîðèòìà îáû÷íî ñóùåñòâåííî òðóäíåå, ÷åì óòâåðæäåíèå òèïà ñóùåñòâóåò àëãîðèòì.  ýòîìñëó÷àå ìû äîëæíû ÷åòêî îïèñàòü âåñü êëàññ ðàññìàòðèâàåìûõ àëãîðèòìîâ. Âûøå áûëî óêàçàíî, ÷òî ëþáîé àëãîðèòì ïîèñêà â óïîðÿäî÷åííîììàññèâå èç n ýëåìåíòîâ ìîæíî ïðåäñòàâèòü â âèäå áèíàðíîãî äåðåâà.Ïîýòîìó äàëåå ìû ðàññìîòðèì íåêîòîðûå ñâîéñòâà áèíàðíûõ äåðåâüåâ.Îïðåäåëåíèå.
Ãëóáèíîé h(x) ëèñòà x â êîðíåâîì äåðåâå D áóäåìíàçûâàòü ÷èñëî ðåáåð â (åäèíñòâåííîì) ïóòè èç êîðíÿ äåðåâà â ëèñò x.Âûñîòîé h(D) äåðåâà D áóäåì íàçûâàòü max h(x), ãäå ìàêñèìóì áåðåòñÿïî âñåì ëèñòüÿì äåðåâà D. Ñðåäíåé âûñîòîé hñð (D) äåðåâà D áóäåìíàçûâàòü ñðåäíåå àðèôìåòè÷åñêîå âåëè÷èí h(x) ïî âñåì ëèñòüÿì äåðåâàD.Ëåììà 1.1. Äëÿ ëþáîãî áèíàðíîãî äåðåâà ñ n ëèñòüÿìè âûïîëíÿþòñÿ íåðàâåíñòâà: 1) h(D) > dlog2 ne, 2) hñð (D) > log2 n.Äîêàçàòåëüñòâî.
1) Ëþáîå áèíàðíîå äåðåâî âûñîòû h ìîæíî äîñòðîèòü äî ïîëíîãî áèíàðíîãî äåðåâà âûñîòû h (â êîòîðîì âñå ïóòè îòêîðíÿ äî ëèñòüåâ ñîäåðæàò ïî h ðåáåð). Äëÿ ýòîãî äîñòàòî÷íî ê êàæäîìóëèñòó x âûñîòû h(x) ïîäêëåèòü ïîëíîå áèíàðíîå äåðåâî âûñîòû h−h(x).Ïðè ýòîì ÷èñëî ëèñòüåâ íå óìåíüøèòñÿ.
Ïîñêîëüêó â ïîëíîì áèíàðíîìäåðåâå âûñîòû 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),òî åñòü ïðîèçâåäåíèå ìàòðèö íå çàâèñèò îò ðàññòàíîâêè ñêîáîê.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
