В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 3
Текст из файла (страница 3)
Îäíàêî÷èñëî îïåðàöèé óìíîæåíèÿ ýëåìåíòîâ ìîæåò ïðè ýòîì îêàçàòüñÿ ðàçíûì.Ïðèìåð. Ïóñòü ìàòðèöû 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 = · · · . .
. ··=2 2 22n!2n−12n−1 (2n − 2)!· (1 · 3 · 5 · . . . · (2n − 3)) ==n!n!(2 · 4 · 6 · · · · · (2n − 2))2n−1 (2n − 2)!1 n−1= C2n−2.n−1n!2 (n − 1)! nÒåîðåìà äîêàçàíà.Çàìå÷àíèå. Äëÿ ïîëíîé ñòðîãîñòè â äîêàçàòåëüñòâå íóæíî îáñóäèòü ñóùåñòâîâàíèå ôóíêöèè f (x), çàäàííîé ðàâåíñòâîì (2.1). Ìîæíîïîêàçàòü, ÷òî ðÿä ñïðàâà ñõîäèòñÿ, íàïðèìåð, ïðè 0 6 x 6 41 .Ðàñêðûâàÿ ôàêòîðèàëû ïî ôîðìóëå Ñòèðëèíãà, ëåãêî ïîëó÷èòü,mm÷òî C2m∼ √4πm , òî åñòü an ðàñòåò ýêñïîíåíöèàëüíî ñ ðîñòîì n.
Ñëåäîâàòåëüíî ïåðåáîðíûé àëãîðèòì èìååò ýêñïîíåíöèàëüíóþ ñëîæíîñòü.Òåîðåìà 2.2. Äëÿ íàõîæäåíèÿ îïòèìàëüíîãî ïîðÿäêà óìíîæåíèÿnìàòðèö ñóùåñòâóåò àëãîðèòì (òèïà äèíàìè÷åñêîãî ïðîãðàì-11ìèðîâàíèÿ) ñ ÷èñëîì îïåðàöèé (àðèôìåòè÷åñêèõ è ñðàâíåíèé ÷èñåë)O(n3 ).Ïóñòü íà âõîä ïîñòóïàåò íàáîð ÷èñåë(m0 , m1 , . .
. , mn ). Ââåäåì òàêèå ïîäçàäà÷è Bij : íàéòè îïòèìàëüíûéïîðÿäîê âû÷èñëåíèé è íàèìåíüøåå ÷èñëî kij óìíîæåíèé ýëåìåíòîâ äëÿïðîèçâåäåíèÿ Ai × Ai+1 × . . . × Aj , (1 6 i 6 j 6 n). Î÷åâèäíî, kii = 0äëÿ âñåõ i, è îáùåå ÷èñëî ïîäçàäà÷ Bij åñòü O(n2 ).Äîêàçàòåëüñòâî.Óòâåðæäåíèå. Åñëè1 6 i < j 6 n,òîkij = min{ki,s + ks+1,j + mi−1 ms mj },(2.2)s òàêèì, ÷òî i 6 s 6 j − 1.Äîêàçàòåëüñòâî.
Åñëè ïîñëåäíÿÿ îïåðàöèÿ óìíîæåíèÿ äåëèò ïðîèçâåäåíèå Ai · Ai+1 · . . . · Aj íà 2 ïðîèçâåäåíèÿ (Ai · . . . · As ) · (As+1 · . . . · Aj ),òî äëÿ ïîëó÷åíèÿ ìèíèìàëüíîãî ÷èñëà îïåðàöèé íàäî èñïîëüçîâàòü ìèíèìàëüíîå ÷èñëî îïåðàöèé â îáåèõ ñêîáêàõ, òî åñòü âñåãî ki,s + ks+1,jîïåðàöèé. Ïîñëå âû÷èñëåíèÿ ýòèõ ïðîèçâåäåíèé íàäî åùå ïåðåìíîæèòü 2ìàòðèöû ðàçìåðîâ mi−1 ×ms è ms ×mj . Ïîëó÷àåì îáùåå ÷èñëî îïåðàöèé,ñòîÿùåå â (2.2) â ôèãóðíûõ ñêîáêàõ. Òåïåðü îñòàåòñÿ çàìåòèòü, ÷òî äëÿìèíèìèçàöèè îáùåãî ÷èñëà óìíîæåíèé äîñòàòî÷íî ïåðåáîðîì âûáðàòüîïòèìàëüíîå ìåñòî äëÿ ïîñëåäíåé îïåðàöèè. Óòâåðæäåíèå äîêàçàíî.Áóäåì ðåøàòü ïîäçàäà÷è Bij ÿðóñàìè, îòíîñÿ ê ÿðóñó t âñå ïîäçàäà÷è ñ j − i = t. Ðàññìîòðèì ïîñëåäîâàòåëüíî t = 0, 1, 2, . .
. , n − 1.Ïðè t = 0 ïîëó÷èì ïîäçàäà÷è Bii , äëÿ êîòîðûõ kii = 0 è ñêîáêè âîîáùåíå íàäî ðàññòàâëÿòü. Ïðè ðåøåíèè î÷åðåäíîé çàäà÷è Bij ñ j − i = tâîñïîëüçóåìñÿ óòâåðæäåíèåì. Ïðè ýòîì ëåãêî âèäåòü, ÷òî ñïðàâà â (2.2)áóäóò èñïîëüçîâàòüñÿ ðåçóëüòàòû ïîäçàäà÷ ÿðóñîâ t1 < t, êîòîðûå óæåðåøåíû. Òîãäà äëÿ âû÷èñëåíèÿ kij ïî ôîðìóëå (2.2) äîñòàòî÷íî ñäåëàòü2(j − i) óìíîæåíèé, 2(j − i) ñëîæåíèé è j − i − 1 ñðàâíåíèé. Îáùåå÷èñëî îïåðàöèé äëÿ âû÷èñëåíèÿ îäíîãî kij íå ïðåâîñõîäèò O(n), à äëÿâû÷èñëåíèÿ âñåõ kij íå ïðåâîñõîäèò O(n3 ) (ïîñêîëüêó îáùåå ÷èñëîïîäçàäà÷ Bij åñòü O(n2 )). Ïðè âû÷èñëåíèè kij óêàçàííûì ñïîñîáîì ìûíàõîäèì è òî s, äëÿ êîòîðîãî äîñòèãàåòñÿ ìèíèìóì â (2.2).
Åñëè ìûäëÿ âñåõ (i, j) áóäåì ôèêñèðîâàòü ýòî s, òî ñìîæåì áûñòðî îïòèìàëüíîðàññòàâèòü ñêîáêè â çàäà÷å B1n (â èñõîäíîé çàäà÷å), ðàçáèâàÿ êàæäîåïðîèçâåäåíèå ïîñëåäîâàòåëüíî îïòèìàëüíûì îáðàçîì íà 2 ïðîèçâåäåíèÿ.Òåîðåìà äîêàçàíà.ãäå ìèíèìóì áåðåòñÿ ïî âñåì12Çàäà÷à î êðàò÷àéøèõ ïóòÿõÏóñòü G ïîëíûé îðèåíòèðîâàííûé ãðàô ñ n âåðøèíàìèv1 , v2 , .
. . , vn . Ïóñòü êàæäîé äóãå (vi , vj ) ñîïîñòàâëåíî äåéñòâèòåëüíîå÷èñëî dij > 0, ëèáî dij = +∞. ×èñëî dij òðàêòóåòñÿ êàê ðàññòîÿíèå èç viâ vj íàïðÿìóþ. Äëèíà îðèåíòèðîâàííîãî ïóòè èç vi â vj îïðåäåëÿåòñÿêàê ñóììà äëèí âñåõ äóã ýòîãî ïóòè (îíà ðàâíà +∞, åñëè õîòÿ áû îäíîñëàãàåìîå ðàâíî +∞).
Êðàò÷àéøåå ðàññòîÿíèå d¯ij èç vi â vj îïðåäåëèìêàê ìèíèìóì äëèí ïî âñåì îðèåíòèðîâàííûì ïóòÿì èç vi â vj . Ñîîòâåòñòâóþùèé ïóòü áóäåì íàçûâàòü êðàò÷àéøèì. Ðàññìîòðèì ñëåäóþùóþçàäà÷ó î êðàò÷àéøèõ ïóòÿõ.Âõîä: ìàòðèöà D = kdij k ïîðÿäêà n (ñ÷èòàåì, ÷òî dii = 0 äëÿ âñåõi).Òðåáóåòñÿ: ïîñòðîèòü ìàòðèöó D̄ = kd¯ij k êðàò÷àéøèõ ðàññòîÿíèé.Îòìåòèì, ÷òî àíàëîãè÷íóþ çàäà÷ó äëÿ íåïîëíîãî ãðàôà ìîæíîñâåñòè ê çàäà÷å î ïîëíîì ãðàôå, ïîëîæèâ dij = +∞ äëÿ íåñóùåñòâóþùèõäóã.
Åñëè dij = dji äëÿ âñåõ i, j , òî ãðàô G ìîæíî ñ÷èòàòü íåîðèåíòèðîâàííûì.Àëãîðèòì äëÿ óêàçàííîé çàäà÷è, îñíîâàííûé íà ïåðåáîðå âñåõâîçìîæíûõ ïóòåé, èìååò íå ìåíåå, ÷åì ýêñïîíåíöèàëüíóþ ñëîæíîñòü,ïîñêîëüêó èç vi â vj ñóùåñòâóåò íå ìåíåå (n−2)! ïóòåé áåç ïîâòîðÿþùèõñÿâåðøèí.Òåîðåìà 2.3. Ñóùåñòâóåò àëãîðèòì äëÿ çàäà÷è î êðàò÷àéøèõD ìàòðèöó D̄, ñ ÷èñëîì îïåðàöèé (àðèô3ìåòè÷åñêèõ è ñðàâíåíèé ÷èñåë) O(n ), ãäå n ÷èñëî âåðøèí â ãðàôå.Äîêàçàòåëüñòâî. Ââåäåì ñëåäóþùèå ïîäçàäà÷è: äëÿ êàæäîé ïàðû(k)i, j è íàòóðàëüíîãî k > 0 âû÷èñëèòü dij ìèíèìàëüíóþ äëèíó ñðåäèâñåõ îðèåíòèðîâàííûõ ïóòåé èç vi â vj , ïðîõîäÿùèõ, êðîìå vi è vj , òîëüêîïî âåðøèíàì v1 , v2 , . . .
, vk (âîçìîæíî òîëüêî ïî ÷àñòè èëè íàïðÿìóþ èçvi â vj ). Åñëè k = 0, òî ðàçðåøàåòñÿ òîëüêî ïåðåõîä èç vi â vj íàïðÿìóþ.(k)Ïóñòü D(k) = kdij k. Òîãäà D(0) = D è D(n) = D̄. Áóäåì ïîñëåäîâàòåëüíîâû÷èñëÿòü D(1) , D(2) , . . . , D(n) .Óòâåðæäåíèå. Äëÿ ëþáûõ i, j è k > 0ïóòÿõ, ñòðîÿùèé ïî ìàòðèöå(k)(k−1)dij = min(dij(k−1), dik(k−1)+ dkj).Âñå ïóòè èç vi â vj , èñïîëüçóþùèå òîëüêî âåðøèíûv1 , v2 , . . . , vk , ðàñïàäàþòñÿ íà 2 ìíîæåñòâà A è B íå ïðîõîäÿùèõ ÷åðåç(k−1)vk è ïðîõîäÿùèõ ÷åðåç vk . Ìèíèìàëüíàÿ äëèíà ïóòåé â A ðàâíà dijïî îïðåäåëåíèþ. Êàæäûé ïóòü èç B ðàçáèâàåòñÿ íà 2 ÷àñòè: ïóòü B1 èçvi â vk ïî âåðøèíàì v1 , v2 , . .
. , vk−1 è ïóòü B2 èç vk â vj ïî âåðøèíàìÄîêàçàòåëüñòâî.13(k−1)v1 , v2 , . . . , vk−1 . Ìèíèìàëüíàÿ äëèíà ïóòè â B1 ðàâíà dik , à â B2 (k)(k−1)(k−1)(k−1)(k−1)+ dkj , ïîëó÷àåì dij . Óòâåðæäåíèåè dikdkj . Ñðàâíèâàÿ dijäîêàçàíî.(k)Çàìå÷àíèå. Âû÷èñëÿÿ dij îïèñàííûì ñïîñîáîì, ìû, â ÷àñòíîñòè,óçíàåì, èñïîëüçîâàòü vk èëè íåò.Òàêèì îáðàçîì, äëÿ âû÷èñëåíèÿ D(k) ïî D(k−1) äîñòàòî÷íî n2 ñëîæåíèé è n2 ñðàâíåíèé ÷èñåë, à äëÿ âû÷èñëåíèÿ D(1) , D(2) , . . . , D(n) = D̄ïî çàäàííîé ìàòðèöå D = D(0) äîñòàòî÷íî n3 ñëîæåíèé è n3 ñðàâíåíèé.Òåîðåìà äîêàçàíà.Ïðè ýòîì, ó÷èòûâàÿ çàìå÷àíèå, ìîæíî áûñòðî óñòàíîâèòü è ñàìèêðàò÷àéøèå ïóòè.2.2. Ìåòîä ðàçäåëÿé è âëàñòâóé. Òåîðåìà îðåêóððåíòíîì íåðàâåíñòâåÄðóãîé ðåêóððåíòíûé ìåòîä ïîñòðîåíèÿ áûñòðûõ àëãîðèòìîâ ýòî ìåòîä, êîòîðûé íàçûâàþò ðàçäåëÿé è âëàñòâóé.
 íåì òàêæå ðåøåíèå çàäà÷è ñâîäèòñÿ ê ðåøåíèþ ïîäçàäà÷, íî, â îòëè÷èå îò ìåòîäàäèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ðàçìåðíîñòü ïîäçàäà÷ îòëè÷àåòñÿ îòðàçìåðíîñòè çàäà÷è íå íà êîíñòàíòó, à â êîíñòàíòó ðàç è ïîäçàäà÷èðåøàþòñÿ íåçàâèñèìî äðóã îò äðóãà. Äëÿ ïîëó÷åíèÿ îöåíîê ñëîæíîñòèòàêèõ àëãîðèòìîâ èñïîëüçóåòñÿ ñëåäóþùàÿ òåîðåìà.Òåîðåìà 2.4 (î ðåêóððåíòíîì íåðàâåíñòâå).
Ïóñòü L(n) ôóíê-n. Ïóñòü c íàòóðàëüíîå ÷èñëî, c > 2, èa, b, α - äåéñòâèòåëüíûå êîíñòàíòû, ïðè÷åì a > 0, è ïóñòü äëÿ âñåõn = ck , ãäå k ëþáîå íàòóðàëüíîå ÷èñëî (k = 1, 2, 3, . . .), âûïîëíÿåòñÿöèÿ íàòóðàëüíîãî ïàðàìåòðàíåðàâåíñòâînL(n) 6 aL( ) + bnα .c(2.3)Ïóñòü ïðè ýòîì L(n) ìîíîòîííî íå óáûâàåò íà êàæäîì îòðåçêå[ck + 1, ck+1 ].
Òîãäà ïðè ñòðåìëåíèè n ê áåñêîíå÷íîñòè äëÿ âñåõ nâûïîëíÿåòñÿαO(n ),L(n) = O(nlogc a ),O(nα log n),åñëèα > logc a,åñëèα < logc a,α = logc a.åñëè îöåíêàõ âèäà O(g(n) logk n), ãäå k êîíñòàíòà, âîñíîâàíèè ëîãàðèôìà ïðåäïîëàãàåòñÿ ëþáîå ïîñòîÿííîå ÷èñëî. Ïðè ýòîìïåðåõîä îò îäíîãî îñíîâàíèÿ ê äðóãîìó èçìåíÿåò òîëüêî êîíñòàíòó â O.Çàìå÷àíèå.14Ïóñòü n = ck , ãäå k = 1, 2, 3, . . .. Òîãäà, ïðèìåíÿÿíåñêîëüêî ðàç (2.3), ïîëó÷àåìÄîêàçàòåëüñòâî. n αnnα) + bnα =L(n) 6 aL( ) + bn 6 a(aL( 2 ) + bcccα= bn + abα6 bn + baαcαα= bn + bnα6 . . . 6 bn + bnαα n αc2+a L2n + a (aLacαacαα+ bnc3 a 2cαnckc2n+ .
. . + bnÏóñòü d = max(b, L(1)). Òàê êàênα+b36 n α+a Lc2n a k−1cα)=c3k6+a Lnck.= 1, òî a k−1 a a 2L(n) 6 dn 1 + α + α + . . . + α+ dak =cccα a 2 a k a.= dnα 1 + α + α + · · · + αcccÐàññìîòðèì 3 ñëó÷àÿ:a< 1 =⇒ L(n) 6 dnα const = O(nα );αca2) logc a > α =⇒ α > 1 =⇒c α 2 α k ! a kαccc=⇒ L(n) 6 dnα α++ ··· +=⇒1+caaa|{z}1)logc a < α =⇒6constlogc a=⇒ L(n) 6 dak const = O(alogc n ) = O(n) (òàê êàê alogc n = nlogc a );3) logc a = α =⇒ a = cα =⇒ L(n) 6 dnα (k + 1) = dnα (1 + logc n) == O(nα log n).Ïóñòü òåïåðü n ëþáîå. Òîãäà ñóùåñòâóåò òàêîå íàòóðàëüíîå k ,÷òî c < n 6 ck+1 . Ðàññìîòðèì 3 ñëó÷àÿ, ó÷èòûâàÿ, ÷òî ïî óñëîâèþ L(n) íåóáûâàþùàÿ ôóíêöèÿ íà êàæäîì îòðåçêå [ck + 1, ck+1 ] (p íèæå k15íåêîòîðàÿ êîíñòàíòà):αα1) α > logc a =⇒ L(n) 6 L(ck+1 ) 6 p(ck+1 ) = pcα (ck ) 6 pcα nα == O(nα );logc a2) α < logc a =⇒ L(n) 6 L(ck+1 ) 6 p(ck+1 )logc a= pclogc a (ck )66 panlogc a = O(nlogc a );α3) α = logc a =⇒ L(n) 6 L(ck+1 ) 6 pc(k+1)α logc (ck+1 ) 6 pcα (ck ) 2k 66 pcα 2nα logc n = O(nα ) log n.Òåîðåìà äîêàçàíà.2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
