Главная Промышленная автоматика.

всех возможных вариантов. Попытайтесь построить эффективный алгоритм для решения этой задачи, используя эвристический подход.

1.10. Рассмотрим следующие функции от л: /,<я) = п; fi(n) = n + 1000л;

л, если л нечетно,

л„ если л четно;

[п, если п<100,

\п, если л>100.

Укажите для каждой пары функций, когда имеет порядок 0(f,{n)) и когда /,(л) есть П(/Дп)). 1.11. Рассмотрим следующие функции от п:

lit для четных л > О, In для нечетных л S 1;

л для о < л < 100, для л > 100;

Укажите для каждой пары функций, когда gi(n) имеет порядок 0(g,{n)} и когда gi(n) есть a(gj{n)).

1.12. Найдите, используя О-символику, время выполнения в наихудшем случае следующих процедур как функции от л:

а) procegure matmpy ( п: integer) ;

i, j, к: integer; begin

for i : = 1 to n do

for J : = 1 to л do begin C[i,j];= 0; for k:= 1 to л do

ClJ.,j]:= Cli.j] + Ali.k] * Blk.j]

б) procegure mystery { л: integer ) ;

i, j, k: integers-begin

for i : = 1 to- n. - i do

for j:= i + 1 to л do for k:= 1 to J do

{группа операторов с временем выполнения 0(1) }

в) procegure veryodd ( л: integer ) ;

i/ j/ x, y. integer;

begin



for 1:- 1 to л do

if нечетноеii) then begin for j:= 1 to л do

x: = x + 1 ; for j:= 1 to i do y:= у + 1

*r> procegure recursive ( n: integer ): integer; begin

if n <= 1 Шеп return(1)

else

return (recursive( л - 1) + recursive{n - 1))

1.13. Докажите, что следующие утверждения истинны:

а) 17 имеет порядок 0(1);

б) п(п - 1)/2 имеет порядок О(п);

в) тахСп, 10п) имеет порядок О(п);

г) есть 0(п**) и ii(n*) для целых k; 1=1

д) если р(х) - полином степени к с положительным старщим коэффициентом, тор(х) есть 0(п*) и

*1.14. Предположим, что TiCn) есть Й(Дп)) и ТгСга) - ii((ra)). Какие из следующих • утверждений истинны?

а) Ti(n)+ Т2(га)есть П(тах(Лп), 1)));

б) Ti(ra)T2(ra) есть ii(An)(ra)).

*1.15. Некоторые авторы определяют нижний порядок роста il следующим образом: f(n) есть если существуют такие неотрицательные константы По и с,

что для всех л > ло выполняется неравенство /(га) > cg(n).

а) В рамках этого определения будет ли истинным следующее утверждение: /(га) есть Q(g(n)) тогда и только тогда, когда g(n) имеет порядок 0(/(п))?

б) Будет ли утверждение а) истинным для определения С1 из раздела 1.4?

в) Выполните упражнение 1.14 для данного определения Ci.

1.16. Расположите следующие функции в порядке степени роста: а) п, б) ып , в) logra, г) log logra, д) logra, е) n/logra, ж) Vralogл , з) (1/3)", и) (3/2)", к) 17.

1.17. Предположим, что параметр л приведенной ниже процедуры является положительной целой степенью числа 2, т.е. л = 2, 4, 8, 16, ... . Найдите формулу для вычисления значения переменной count в зависимости от значения л.

procegure mystery ( п: integer ) ; var

X, count: integer; begin

count-. = 0;

x:= 2;

while X < П do begin

k:= 2 * x;

count: = count + 1

УПРАЖНЕНИЯ 43



end;

writeln (count)

1.18. Рассмотрим функцию max(i, n), которая возвращает наибольший из элементов, стоящих в позициях от i до i + я - 1 в целочисленном массиве А. Также предположим, что я является степенью числа 2. procegure max ( i, п: integer ) : integer; var

jnl, ш2: integer; begin

\i n = \ then

return(Л[i]) else bedin

ш1: = шах (i, n div 2) ; jn2: = max(i+n div 2, я div 2) ; if ml < ml then return (ml)

else

return (л!1)

а) Пусть T(n) обозначает время выполнения в наихудшем случае программы max в зависимости от второго аргумента га. Таким образом, я - число элементов, среди которых ищется наибольший. Запишите рекуррентное соотношение для Т(п), в котором должны присутствовать Т(у)для одного или нескольких значений у, меньших я, и одна или несколько констант, представляющих время выполнения отдельных операторов программы max.

б) Запишите в терминах О-большое и П верхнюю и нижнюю границы для Т(п) в максимально простом виде.

Библиографические замечания

Концепция абстрактных типов данных берет свое начало от типа class в языке SIMULA 67 [12]. С тех пор разработано много языков программирования, поддерживающих абстрактные типы данных, среди которых язык Alphard [100], С с классами [105], CLU [69], MESA [42] и Russell [23]. Концепция АТД активно обсуждалась в работах [43] и [122].

[63] - первая большая работа, посвященная систематическому изучению времени выполнения программ. Авторы этой книги в более ранней работе [3] связали временную и емкостную сложности алгоритмов с различными моделями вычислений, таких как машины Тьюринга и машины с произвольным доступом к памяти. Другие библиографические ссылки на работы, посвященные анализу алгоритмов и программ, приведены в библиографических замечаниях к главе 9.

Дополнительный материал о структурном программировании вы найдете в [50], [60], [120] и [125]. Производственные и философские вопросы организации больших программных проектов обсуждаются в работах [15] и [115]. В [61] показано, как создавать полезные программные инструменты для сред программирования.





0 1 2 3 4 5 6 7 8 9 [10] 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002