Полезная методичка

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ	3
1. РЕКУРРЕНТН Е УРАВНЕНИ	11

1.1.ПОН ТИЕ РЕКУРРЕНТНОГО УРАВНЕНИ . . . 11

1.2.СПОСОБ РЕ ЕНИ

РЕКУРРЕНТН Х УРАВНЕНИЙ . . . . . . . . . . . 12

1.3.ТЕОРЕМА О РЕ ЕНИИ

РЕКУРРЕНТНОГО УРАВНЕНИ . . . . . . . . . . . 18

1.4.ПРИМЕР . . . . . . . . . . . . . . . . . . . . . . . . 20

2. СОРТИРОВКА

22

2.1.ОСНОВН Е ПОН ТИ И ОПРЕДЕЛЕНИ . . . . 22

2.2.СОРТИРОВКА С ПОМО

ÏÐ ÌÎÃÎ ÂÊË ×ÅÍÈ . . . . . . . . . . . . . . . 24

2.3.СОРТИРОВКА С ПОМО ПР МОГО В БОРА 26

2.4.ОБМЕНН Е АЛГОРИТМ . . . . . . . . . . . . . . 27

2.4.1Пу ырько я сортиро к . . . . . . . . . . . . . 27

2.4.2йк рн я сортиро к . . . . . . . . . . . . . . 28

2.5.СОРТИРОВКА СЛИ НИЕМ . . . . . . . . . . . . . 29

2.6.СОРТИРОВКА С ПОМО РАЗДЕЛЕНИ . . 31

2.7.НАХОЖДЕНИЕ k-ÎÃÎ

НАИМЕН ЕГО ЛЕМЕНТА . . . . . . . . . . . . 33

2.8.ЛЕКСИКОГРАФИЧЕСКА СОРТИРОВКА . . . . . 36

3.РАЗРАБОТКА ФФЕКТИВН Х АЛГОРИТМОВ 39

3.1.МЕТОД РАЗДЕЛ Й И ВЛАСТВУЙ . . . . . . . . . 39

3.2.ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ . . . . 41

4. СТРУКТУР ДАНН Х

49

4.1.СТРУКТУР ДАНН Х: СПИСКИ, СТЕКИ, ОЧЕ- РЕДИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.1.1Лин йны списки и о ы оп р ции н ними 51

4.1.2Ñò êè è î û îï ð öèè í íèìè . . . . . . 57

1

4.1.3Î÷ ð è è î û îï ð öèè í íèìè . . . . . 59

4.2.ГРАФ . ОСНОВН Е ОПРЕДЕЛЕНИ И СПО-

СОБ ЗАДАНИ . . . . . . . . . . . . . . . . . . . .	61
4.3. ДЕРЕВ . ОСНОВН Е ОПРЕДЕЛЕНИ И СПО-
СОБ ЗАДАНИ . . . . . . . . . . . . . . . . . . . .	65

4.4.МНОЖЕСТВА . . . . . . . . . . . . . . . . . . . . . . 72

4.4.1Пр ст л ни мно ст с помощью списко . 72

4.4.2Пр ст л ни мно ст с помощью корн ыхр ь . . . . . . . . . . . . . . . . . . . . . . 77

4.5.ПРИОРИТЕТН Е ОЧЕРЕДИ . . . . . . . . . . . . . 84

4.5.1 Áèí ðíû êó÷è . . . . . . . . . . . . . . . . . . 85

4.5.2D-Êó÷è . . . . . . . . . . . . . . . . . . . . . . . 99

4.5.3 Биноми льны кучи . . . . . . . . . . . . . . . 106

4.5.4Êó÷è Ôè îí ÷÷è . . . . . . . . . . . . . . . . . 116

5. ПОИСКОВ Е ДЕРЕВ

132

5.1.БИНАРН Е ПОИСКОВ Е ДЕРЕВ . . . . . . . . 132

5.2.СБАЛАНСИРОВАНН Е ДЕРЕВ . . . . . . . . . 137

5.2.1 ÀÂË ð üÿ . . . . . . . . . . . . . . . . . . . 137

5.2.22-3 ð üÿ . . . . . . . . . . . . . . . . . . . . . 153

6. ОСНОВН Е АЛГОРИТМ НА ГРАФАХ	171
6.1. ПОИСК В ГЛУБИНУ В ГРАФЕ . . . . . . . . . . . .	171
6.2. ПОИСК В ИРИНУ В ГРАФЕ . . . . . . . . . . . .	176

6.3.КРАТЧАЙ ИЙ ПУТ В ГРАФЕ . . . . . . . . . . . 180

6.4.МАКСИМАЛ Н Й ПОТОК В ГРАФЕ . . . . . . . . 184

6.5.МИНИМАЛ НОЕ ОСТОВНОЕ ДЕРЕВО ГРАФА . . 194

6.6.ТОПОЛОГИЧЕСКА СОРТИРОВКА . . . . . . . . 200

Ëèò ð òóð

207

2

ВВЕДЕНИЕ

Сн ч л н помним н которы с ния и т ории роятности. В т ории информ ции р чь с и т о ситу циях, которых мы н лю м со ытия, что ы и них с л ть ы о о ру их со ы- тиях. Информ ция сть н что, что исит от ух щ й. Т к, получ я информ цию по т л и нию и но ост й, мы ср ни -м с у им ющ йся у н с (со р ни информ ции по торно просмотр нном ыпуск но ост й сть ноль).

Информ цию, которую получ ют о со ытии A , í ëþ ÿ ñî û- òè B , î î í ÷ þò I(A; B) è îïð ëÿþò

def	P (A	B)
I(A; B) = logb	j		;
	P (A)

P (A); P (B) =6 0 è P (AjB) роятность то о, что со ыти A ïðîè îé ò, ïðè óñëî èè, ÷òî ñî ûòè B ó ïðîè îøëî.

Åñëè ê ÷ ñò îñíî íèÿ ëî ðèôì ÿòü 2 , то иниц й и - м р ния информ ции у т ит.

Í ñëî íî ïîê òü, ÷òî

I(A; B) = I(B; A);

то сть н им т н ч ния, получ м мы информ цию о со ытии B , í ëþ ÿ A èëè í î îðîò ( I(A; B) имн я информ ция со ытий A è B ).

Пусть со ытия A è B н исимы, то P (AjB) = P (A) è
I(A; B) = log2	P(AjB)	= log2 1 = 0:
	P (A)

Пусть P (AjB) = 1 , ÷òî î îðèò î òîì , ÷òî ñî ûòè A î ÿ - ò ëüíî ïðè îé ò, ñëè ñî ûòè B ó ïðîè îøëî. Òî

1

I(A; B) = log2 P (A) = log2 P (A)

è I(A; B) = log2 P(A) сть то колич ст о информ ции, которо оост точно ля н ния то о, что со ыти A ïðîè îøëî.

3

Для со ст нной информ ции со ытия A ìî íî ïèñ òü

I(A) = log2 P (A):

Ïðèì ð 1.

Пусть им тся 8 ильяр ных ш ро , пронум ро нных от 1 î 8 . К ко о колич ст информ ции ост точно ля уст но л ния ном р ы р нно о случ йным о р ом ш р ?

Т к к к лю ой ш р мо т ыть ы р н с р ной роятностью, то роятность со ытия A , êëþ÷ þù îñÿ îïð ë íèè íîì ðû ð ííî î ø ð ñòü P(A) = 1=8 è I(A) = log2(1=8)) = 3 .

Ïðèì ð 2.

Пр поло им, что н хо поступ т н которо число A , которо мо т ыть ы р но и инт р л [1; ; m] , прич м лю ойы ор я ля тся р но роятным. То I(A) = dlog2 me колич - ст о ито , которо н о хо имо ля опр л ния то о, к ко конкр тно число мы ы р ли.

Р м рностью чи l у м н ы ть колич ст о инфор- м ции, которой ост точно ля форм льно о опис ния чи. Если пр поло ить, что р м рность м шинно о сло ост точнля р руш ния н опр л нности (пр ст л ния) ля н которо-о числ , то р м рность чи у т р н числу исхо ныхнных форм ли о нном и .

Ïðèì ð 3.

Пр поло им, что н хо н которо о л оритм поступ ют

÷èñë : a è b . То р м рность чи (т. . колич ст о информ - ции, ост точной ля ния этих чис л), р н l = l1 + l2 ,

l1 = dlog2 ae è l2 = dlog2 be .

Ïðèì ð 4.

Пр поло им, что н хо поступ т n ÷èñ ë fa1; a2; ; ang . Р м рность чи сть

n

l = Xdlog2 aie:

i=1

Если пр поло ить, что р м рности м шинно о сло ост точ-

íî ëÿ ïð ñò ë íèÿ ëþ î î è ÷èñ ë (ò. . maxi=1; ;ndlog2 aie const ), то р м рность чи l мо но оц нить личиной C n .

Вр мя, тр чи мо л оритмом, к к функция от р м рно-

4

сти чи, н ы тся р м нной сло ностью л оритм . то функция, котор я ч р м рности l ñò èò ñîîò òñò è ì ê- ñèì ëüíî ð ìÿ f(l) , тр чи мо л оритмом ля р ш ния. О ъ м п мяти, тр у мый ля р ли ции л оритм , к к функция от р м рности чи, н ы тся мкостной сло ностьюл оритм . По ни р м нной ( мкостной) сло ности при у - лич нии р м рности чи о скон чности н ы тся симптотич ской р м нной сло ностью ( симптотич ской м- костной сло ностью).

Если при нной р м рности к ч ст м ры сло ности - р тся н и ольш я и сло ност й (по с м хо м этой р м рности), то он н ы тся сло ностью ху ш м случ . Если при нном р м р к ч ст м ры сло ности р тся ср няя сло ность (по с м хо м нной р м рности), то он н ы -тся ср н й или уср н нной сло ностью. О ычно ср нюю сло ность н йти тру н , ч м сло ность ху ш м случ . О н - ко, н сл у т ы ть, что л оритм с н им ньш й сло ностью ху ш м случ н о я т льно им т лучшую скорость ср н м.

Если н который л оритм о р ты т хо ы лины n ð - ìÿ Cn2 , C н котор я конст нт , то о орят, что р м нн я

сло ность это о л оритм сть O(n2) ("ïîðÿ ê n2 ").

В о щ м случ , у м о орить, что н отриц т льн я функция

	T (n) ñòü O(f(n)) , сли сущ ст у т т к я конст нт C	è
	n0 , ÷òî T(n) Cf(n) ëÿ ñ õ n n0 ;
	T (n) ñòü (f(n)) , сли сущ ст у т т к я конст нт C è n0 ,
	÷òî T (n) Cf(n) ëÿ ñ õ n n0 ;
	T (n) ñòü (f(n)) , то и только то , ко T (n)	=
	= O(f(n)) è T (n) = (f(n)) .

Для ссимптотик спр ли ы сл ующи пр ил :

1.Åñëè f(n) ñòü O(g(n)) è g(n) ñòü O(h(n)) , òî f(n) ñòü

O(h(n)) .

2. Åñëè f(n) ñòü O(kg(n)) ля н которой конст нты k > 0 , òî f(n) ñòü O(g(n)) .

5

3.Åñëè f1(n) ñòü O(g1(n)) è f2(n) ñòü O(g2(n)) , òî f1(n) +

+ f2(n) ñòü O(max(g1(n); g2(n))) .

4.Åñëè f1(n) ñòü O(g1(n)) è f2(n) ñòü O(g2(n)) , òî f1(n) f2(n) ñòü O(g1(n) g2(n)) .

Р ны л оритмы им ют р личную р м нную сло ность. Для ср н ния эфф кти ности л оритмо ч сто прим ня тся о ин простой по хо , который ключ тся р личии м у полиноми льными и экспон нци льными л оритм ми.

Полиноми льным л оритмом (или л оритмом полиноми льной р м нной сло ности) н ы тся л оритм, у которо о р м нн я сло ность р н f(l) = O(p(l)) , p(l) н котор я полиноми льн я функция, l р м рность чи.

Ал оритмы, у которых р м нн я сло ность р н f(l) = = (exp(l)) , exp(l) н котор я экспон нци льн я функция, н ы ются экспон нци льными.

Р личи м у полиноми льными и экспон нци льными л о- ритм ми осо нно м тно при р ш нии ч ольшой р м рности.

Вр м нн я сло ность	n = 10	n = 20	n = 30
n	0.00001c	0.00002c	0.00003c
n2	0.0001c	0.0004c	0.0009c
n3	0.001c	0.008c	0.027c
n5	0.1c	3.2c	24.3c
2n	0.001c	1c	17.9 ìèí.
3n	0.059c	58 ìèí.	6.5 ë ò

Сл у т отм тить оч нь ыстрый рост ух при нных экспон нт. Р личи м у полиноми льными и экспон нци льнымил оритм ми проя ля тся щ ол у ит льно, сли про н ли-иро ть лияни у лич ния ыстро йст ия ВМ н р мя р -оты л оритмо . Т к ля функции f = 2n у лич ни скоростиычисл ний 1000 р при о ит лишь к тому, что р м рность н и-

ольш й чи, р р шимой о ин ч с, о р ст т только н 10,то р мя к к ля функции f(n) = n5 эт р м рность о р -

ст т почти 4 р . Т ким о р ом, колосс льный рост скорости

6

ычисл ний, ы нный поя л ни м нын шн о покол ния цифро-ых ычислит льных м шин, н ум ньш т н ч ни эфф кти ныхл оритмо .

С ру ой стороны, н которы экспон нци льны л оритмы

сьм эфф кти ны н пр ктик , ко р м ры р ш мых ч н лики. Т к функция f(n) = 2n ò ñ ÿ ëó÷ø , ÷ ì f(n) = n5

ïðè n 20 ). Кром то о, и стны н которы экспон нци льныл оритмы, сьм хорошо р ком н о ши с я н пр ктик . Д ло том, что р м нн я сло ность опр л н к к м р по -

ния л оритм н иху ш м случ (ут р ни о том, что л-оритм им т р м нную сло ность 2n , î í ÷ ò, ÷òî ð ø íè ïî

кр йн й м р о ной чи р м рности n òð ó ò ð ì íè ïîðÿ - ê 2n ) н с мом л мо т ок ться, что ля ольшинст ру-их ч тр ты р м ни н чит льно м ньш (симпл кс-м то , м то т й и р ниц р ш ния чи о рюк к ).

Сл у т отм тить, что ольшинст о экспон нци льных л оритмо это просто ри нты полно о п р ор . З ч счит тся хорошо р ш мой, сли ля н получ н полиноми льный л оритм,проти ном случ чу н ы ют "тру нор ш мой".

Для то о, что ы ычислять сло ность л оритм , н о хо и- мо опр лить мо ль ычислит льно о устройст , которо исполь у тся ля р ли ции л оритм , т к усло иться, что поним ть по эл м нт рным ш ом ычисл ния. Мы у м исполь-о ть р но оступную р сную м шину (РАМ), котор я пр ст ля т и с я ычислит льную м шину с о ним сумм тором, котором ком н ы про р ммы н мо ут и м нять с ми с я. РАМ состоит и хо ной л нты, с которой он мо т только считы-ть, ыхо ной л нты, н которую он мо т только писы ть, и п мяти, котор я состоит и посл о т льности р истро . С м про р мм посл о т льность ком н , он н писы тся п мять.

Для РАМ про р ммы р м нн я сло ность ху ш м случ

это функция f(n) , ð í ÿ í è îëüø é (ïî ñ ì õî ì ëèíû n ) и сумм р м н, тр ч нных н к ую ср от шую ком н у. Ан ло ично, ля РАМ про р ммы мкостн я сло ность ху ш м случ это функция f(n) , р н я н и ольш й (по с м хо млины n ) и сумм мкост й с х р истро , к которым ыло о р - щ ни . Т п рь н м ост лось опр лить р мя, н о хо имо ля

7

ыполн ния к ой РАМ ком н ы и о ъ м п мяти, исполь у мый к ым р истром. Для это о сущ ст у т ря крит ри , мы у м

льн йш м исполь о ть р ном рный со ой крит рий :

к я ком н тр чи т о ну иницу р м ни;

к ый р истр исполь у т о ну иницу п мяти.

Учиты я с л нно р н пр поло ни о том, что ля р ру- ш ния н опр л нности н которо о числ н м ост точно о но о м шинно о сло , получ м, что мкостн я сло ность л оритм (р м рность п мяти), ля ния n ýë ì íòî ñòü O(n) .

Р ссмотрим к ч ст мо ифик ций РАМ сл ующи мо-ли: н т ящуюся мо ль и р ья р ш ний.

Í ò ÿù ÿñÿ ìî ëü

Пусть тр у тся ычислить н ч ни полином : p(x) = anxn +

+ an 1xn 1 + + a1x + a0 .

Âõî : a0; a1; ; an ; í îïð ë íí ÿ ï ð ì íí ÿ x ; Âûõî : p .

Ïî ïð èëó Ãîðí ð :

n = 1; p(x) = a1x + a0 ;

n = 2; p(x) = (a2x + a1)x + a0 ;

n = 3; p(x) = ((a3x + a2)x + a1) x + a0 ;

Ìû ð ðí ì ïðî ð ììó ëÿ ê î î n , копируя по торяющи ся ком н ы тр у мо число р . В р ульт т получим посл -о т льность н т ящихся про р мм ( цикло ). Длины этих про р мм о р ст ющ й лины. Для к ой лины n î í ïðî-ð ìì .

n = 1	n = 2	n = 3
a1 x ! t	a2 x ! t	a3 x ! t
t + a0 ! p	t + a1 ! t	t + a2 ! t
	t x ! t	t x ! t
	t + a0 ! p	t + a1 ! t
		t x ! t
		t + a0 ! p

8

Т ким о р ом, сли к ч ст мо ли ычисл ний ять н т-ящуюся про р мму, то р м нн я сло ность посл о т льности про р мм р н числу ш о n -ой про р ммы, к к функции от n . Н ор ш о н т ящ йся про р ммы мо т ыть пр ст л н сл ующим о р ом:

y + z ! x

y z ! x y z ! x y=z ! x i ! x

Т ким о р ом, р м нн я сло ность: 2n число рифм тич - ских оп р ций. Емкостн я сло ность: n+ 4 число п р м нных про р мм . Сл о т льно, ычисл ни полином по сх м Горн р им т р м нную и мкостную сло ность поря к O(n) .

Ä ð üÿ ð ø íèé

В н которых ч х у о но к ч ст осно ной м ры сло ностир ть число ыполня мых ком н р т л ния. В случ сортиро ки, р умно р ссм три ть т кую мо ль, которой с ш иют р т л ния, о ник ющи р ульт т ср н ния ух - личин. Т кую про р мму пр ст ляют и оично о р . К ый у л т ко о р о ин и ш о р ш ния. Ну ныйыхо н хо ится о ном и листь .

Вр м нн я сло ность р р ш ний р н ысот р , к к функции р м рности чи ( ысот р сть путь м ксим льной лины и корня о лю о о и листь ), т к к к о ычно мы хотим и м рить н и ольш число ср н ний, которы прихо итсял ть, что ы н йти ну ный путь от корня к листу. З м тим, что о щ число у ло р мо т н чит льно пр осхо ить оысоту. Н прим р, р о р ш ний ля сортиро ки n ÷èñ ë îë - íî ñî ð òü ïî êð éí é ì ð n! листь , хотя о ысот мо тыть n log n .

Ïðèì ð 5.

Опр лить р м нную сло ность л оритм сло ния п р ых n н тур льных чис л.

Т к к к н хо поступ т н которо число n , то р м рность

ííîé ÷è ñòü l = log	2	n ( n = 2l ).
		9

Если ля ычисл ния суммы исполь у тся сл ующий л о- ритм:

S := 0;

for i := 1 to n do

S := S + i;

то колич ст о оп р ций л оритм р но (n) , è ò ê ê ê n = 2l , то нный л оритм я ля тся экспон нци льным.

Если ля н хо ния суммы п р ых n чис л исполь о ть формулу суммы рифм тич ской про р ссии:

S := n(n + 1) ; 2

то колич ст о оп р ций р но конст нт (O(1)).

Сл у т отм тить, что сли при нным ыш л оритмом н - хо ить сумму прои ольных чис л fa1; a2; ; ang , то р м рность

÷è ñòü l = (n) (см. Прим р 4) и л оритм я ля тся полиноми льным.

Ïðèì ð 6.

Опр лить, я ля тся ли н которо число x простым.

Р м рность нной чи сть l = log		2	x ( x = 2l ). Ð ø òü
÷ó ó ì ñë ующим л оритмом:
for	i := 2 to px do
if x	mod i =0 then

{ число н просто ; exit; }

Колич ст о оп р ций л оритм р но (px) . Вр м нн я сло - ность л оритм сть (2l=2) = (exp(l)) . Д нный л оритм опр -

л ния простоты числ я ля тся экспон нци льным.

Óïð í íè .

Опр лить р м нную сло ность л оритм ычисл ния n! ,

который при н ни .

T := 1;

for i := 1 to n do

T := T i;

10