Дудаков С.М. Математическое введение в информатику

Подождите немного. Документ загружается.

7.3. Время и память вычисления 211

Пример 7.5. См. пример 7.1 на стр. 203. Мы уже видели, что для

нашей первой программы время работы не зависит от начального со-

стояния τ, следовательно,

(n) = Tm

(n) = 5.

Используемая память равна

(τx) + 2

(τy) + 1 = 2 (

(τx) +

(τy)) + 1 = 2n + 1,

поэтому

(n) = Sp

(n) = 2n + 1.

Пример 7.6. См. пример 7.2 на стр. 204. Сначала найдем максималь-

ные время и память.

(n) = max {Tm (Π, τ) :

(τ) = n} =

= max {8 + 9 (τ x − τy) : [log

x] + 1 + [log

y] + 1 = n}.

Очевидно, что для достижения максимума нужно взять состояние

τ такое, что τy = 0, а x выбрать максимальным при условии, что

[log

τx] = n − 2. Очевидно, что τx должно быть равно 2

n−1

− 1. По-

этому,

(n) = 8 + 9



n−1

− 1 − 0



= 4.5 · 2

− 1.

Память является максимальной при тех же условиях, поэтому

(n) = 4 (n − 1) + 1 + n − 1 = 5n − 4.

Точные средние оценки в данном случае мы получать не будем вви-

ду их сложности. Получим приближенную оценку среднего времени.

Очевидно, что

(n) =

(τ)=n

(8 + 9b τ x − τyc) = 8 +

(τ)=n

bτx − τyc.

Чтобы найти последнюю сумму, заметим, что

(τ)=n

bτx − τyc =

(τ )=n

τ x≥τ y

τx − τy ≈

(τ )=n

(τ x)≥

(τ y)

τx − τy.

212 Глава 7. Вычислительная сложность

Прежде, чем продолжать, выведем формулу для суммы всех чисел дли-

ны n:

(x)=n

x =

−1

x=2

n−1

x = 2

n−1

· 2

n−1

−1

x=0

x =

= 2

2n−2

n−1



n−1

− 1



2n−2

−

n−1

Найдем нашу сумму, когда длины x и y зафиксированы:

(x) = i,

(y) = n − i.

(x)=i;

(y)=n−i

x − y = 2

n−i−1

(x)=i

x − 2

i−1

(y)=n−i

y =

= 2

n−i−1



2i−2

−

i−1



− 2

i−1



2n−2i−1

−

n−i−1



n+i−3

−

n−2

−

2n−i−3

n−2

n−3



− 2

n−i



Теперь просуммируем по всевозможным i от n/2 до n − 1 (то есть,

когда

(x) ≥

(y)):

n−1

i=n/2

n−3



− 2

n−i



n−3





n−1

i=n/2

− 2

n−1

i=n/2

−i





n−3



n/2



n/2

− 1



− 2

−n/2

1 − 2

−n/2

1 − 2

−1



n−3



− 2

n/2

− 2



n/2

− 1



n−3



− 3 · 2

n/2

+ 2



2n−3



1 − 3 · 2

−n/2

+ 2

−n+1



≈

2n−3



1 − 3 · 2

−n/2



К этой сумме необходимо прибавить слагаемое, описывающее случай

y = 0:

2n−4

−

n−2

2n−3



−

−n+1



≈

2n−3

Всего получается

2n−3



1 − 3 · 2

−n/2



2n−3

7.3. Время и память вычисления 213

2n−3



− 3 · 2

−n/2



2n−2



1 − 2

−n/2+1



Таким образом, мы получили приближенное равенство:

(τ)=n

bτx − τyc ≈

2n−2



1 − 2

−n/2+1



Теперь найдем общее количество начальных состояний длины n. Най-

дем количество z таких, что

(z) = i. Имеем

[log

z] + 1 = i, 2

i−1

≤ log

z ≤ 2

− 1.

Общее количество z, следовательно, равно 2

i−1

. Если

(x) = i,

(y) =

n − i, то количество таких состояний есть

i−1

· 2

n−i−1

= 2

n−2

Поэтому общее количество состояний длины n есть (n − 1) 2

n−2

. При-

бавим еще случаи, когда x = 0 или y = 0, получим: (n + 1) 2

n−2

. Отсюда

мы можем получить приближенную оценку для среднего времени:

≈ 8 + 9

2n−2



1 − 2

−n/2+1



(n + 1) 2

n−2

= 8 + 9

8 (n + 1)



1 − 2

−n/2+1



= 8 +

8 (n + 1)



− 2

n/2+1



Посмотрим, насколько точная оценка получилась. Пусть, например,

n = 4. Имеется 2 числа длины 1: 0 и 1, 2 числа длины 2: 2 и 3, и 4 числа

длины 3: 4, 5, 6 и 7. Всего состояний τ таких, чтобы

(τx)+

(τy) = 4,

следовательно, им еется:

N = 2 · 4 + 2 · 2 + 4 · 2 = 20.

Найдем теперь сумму

(τ)=4

bτx − τyc = 4 + 5 + 6 + 7 + 3 + 4 + 5 + 6 + 1 = 41.

214 Глава 7. Вычислительная сложность

Поэтому точное среднее время для n = 4 есть:

(4) = 8 + 9 ·

· 41 ≈ 26.5.

Наша формула дает:

(4) = 8 +

8 · 5

(16 − 8) = 24.2.

Точно так же можно проверить результат и для n = 5; 6. При n = 5

точная оценка: 45.5, приближенная: 43. При n = 6 имеем 79.5 и 77.5

соответственно. Как видим, оценка является очень точной даже для

маленьких n.

∗

Задача 7.8. Найдите оценку для средней памяти.

Предметный указатель

, 22

<ω

, 22

, 180

P(A), 23

, 38, 147

, 84

V, 32

(Π)

, 90

(a)

...

, 58

)

, 23

)

i=x

, 23

(σ)

...

, 60

=, 21

≡, 30

f(a

, . . . , a

), 20

, 20

{ϕ}Π {ψ}, 106

, 117

7→, 20

|=, 43, 105

6|=, 43, 105

x, y, 33

, 20

, 44

σ(T), 43

σ(e), 42

, 50

∼, 33

B, 105

Alg, 38

arg, 38

Cnt, 201, 202

Ct, 191

do, 35

dom, 23

else, 35

end, 35, 38

Fc, 153, 154, 156

Ff, 158

Fs, 156

Ft, 157

if, 35

LVar, 36

Res, 50, 147

rng, 23

, 198, 207

Sp, 207, 210

, 210

Start, 84

succ, 32

then, 35

Tm, 207, 210

, 210

Var, 36

while, 35

АКС, 109

216 Предметный указатель

Аксиомы, 104

Алгоритм, 9, 38

Евклида, 17

детерминированный, 13

итерационный, 17

конечный, 13

недетерминированный, 13

полууниверсальный, 14

рекурсивный, 17

универсальный, 13

частный, 14

Аргументы подпрограммы, 146

ВП, 182

ВП*, 184

Верификация программы, 131

Вершина

внутренняя, 26

графа, 25

Время

вычисления, 207

максимальное, 210

среднее, 210

Вывод, 104

Выводимость, 105

Вызов

алгоритма, 50

подпрограммы, 147

рекурсивный, 158

Выражение, 33, 147

Вычисление

выражения, 201

программы, 202

теста, 202

Вычисление функции алгорит-

мом, 50

Граф, 24

зависимости, 152

нагруженный, 25

размеченный, 25

ДОБ, 125, 183

ДТС, 191

Дерево, 26

вложенных вызовов, 157

троек-состояний, 191

Длина входа, 209

Доказательство, 104

Доказуемость, 105

Допустимость, 124

Дуга

графа, 25

ЗАМ, 184

ЗП, 181, 182

Замена

метки, 90

переменных, 58

в состоянии, 60

Зацикливание, 45

Значение

выражения, 42, 148

переменной, 42

теста, 43

формулы, 29

атомной, 29

функции, 20

Имя

алгоритма, 38

переменной, 32

подпрограммы, 146

Инвариант

программы, 114

частичный, 114

цикла, 116

Предметный указатель 217

частичный, 116

Информатика, 9

Исполнитель, 9

Истинность

теста, 43

условия, 105

Исчисление, 104

Хоара, 109

предусловий, 132

Квантор

всеобщности, 29

существования, 29

Композиция отображений, 21

Константа, 32

Корень дерева, 26

Корректность

полная, 107

программ, 112

частичная, 106

Лемма

о бесконечных деревьях вызо-

вов, 159

о вложенных вызовах, 156

о вычислении

выражений, 205

программ, 206

о замене метки, 90

о замене переменной

в выражениях, 61

в программах, 62

в тестах, 62

о кодировании пар чисел, 172

о конечности ДТС, 195

о конечных ДТС, 192

о конечных деревьях, 159

о конечных деревьях вызовов,

161

о корректности ВП, 196

о косвенной рекурсии, 173

о минимальном объеме, 199

о множествах вызовов, 194

о неиспользуемых перемен-

ных, 57

о полной корректности цикла,

118

о представлении предусловий,

142, 143

о разложении выражения, 68

о результате замены, 59

о сбалансированности, 39

о сохранении значения, 56

о суффиксе программы, 40

о существовании предусловий,

144

о форме предусловий, 141

об обратимости замены, 60

об определенности вложенных

вызовов, 160

об убывающих цепях, 24

об упрощении

неполного ветвления, 70

полного ветвления, 69

цикла, 70

Лес, 27

вложенных вызовов, 158

Лист дерева, 26

Ложность

теста, 43

условия, 105

Мера сложности, 209

Метка, 83

завершающая, 84

заключительная, 84

начальная, 84

218 Предметный указатель

оператора, 84

перехода, 84

Множество

вершин, 24

вложенных вызовов, 156

дуг, 24

значений, 23

переменных, 36

изменяемых, 36

ребер, 24

НВ, 109

Начальное состояние вызова, 50

Непротиворечивость исчисления

Хоара, 110

предусловий, 132

ОП, 109

Область

определения, 23

Объем памяти, 198

Ограничение функции, 20

Ограничитель

вызовов, 180

цикла, 117

универсальный, 117

Оператор, 33

ветвления, 83

неполного ветвления, 35

полного ветвления, 35

присваивания, 33, 83

левая часть, 33

правая часть, 33

простой, 67

цикла, 35

Операторы

следование, 35

Операция, 32

Ослабление постусловия, 109

Отображение, 19

частичное, 21

ПВ, 109

ПРИСВ, 124

ПРИСВ*, 124

Память

вычисления, 207

максимальная, 210

состояния, 207

средняя, 210

Параметры подпрограммы, 146

Переменная, 32

входная, 38

выходная, 38

Поддерево, 27

Подпрограмма, 146

рекурсивная, 153

Полнота исчисления, 139

Хоара, 139

предусловий, 140

Последовательность, 23

Построение программы

простой, 72

с метками, 93

структурированной, 98

функциональной, 163

Постусловие, 106

Правила вывода, 104

Правило

вызова подпрограммы, 182

замены переменной

для присваиваний, 181

для тестов, 182

неполного ветвления, 109

полного ветвления, 109

следование, 109

Предметный указатель 219

Предметная область, 31

Предусловие, 106

слабейшее, 131

полное, 132

Префикс, 33

собственный, 33

Программа, 10

аппликативная, 163

основная, 152

простая, 67

с метками, 83

структурированная, 35

структурная, 35

функциональная, 163

Произведение отображений, 21

Путь на графе, 26

Разрешимость, 12

Ребро

графа, 25

Результат вызова, 50, 147

Рекурсия, 153

косвенная, 153

прямая, 153

СЛ, 109

СНВ, 133

СПВ, 134

СПР, 132

ССЛ, 133

СЦП, 134

СЭП, 133

Связки булевы, 28

Семантика, 9

неполного ветвления, 44

полного ветвления, 44

присваивания, 44

программы, 150

с метками, 85

структурированной, 44

следования, 44

цикла, 45

Символ кванторный, 28

Синтаксические конструкции,

104

Следствие

о двойном представлении про-

граммы, 41

о двух состояниях, 58

о разложении теста, 68

о результате, 58

об эквивалентности предусло-

вий, 132

упрощение присваиваний, 68

Совпадение

графическое, 33

Состояние, 42

программы, 42

расширенное, 84

Спецификация программы, 130

Список, 24

вложенных вызовов, 153, 154,

156

входных переменных, 38

Суффикс, 33

собственный, 33

Тело

алгоритма, 38

подпрограммы, 147

Теорема

о подстановке, 76

о полноте исчисления

Хоара, 140

предусловий, 140

о представлении формул, 142

220 Предметный указатель

о представлении функций, 141

о простой программе, 72

о семантике следования, 49

о структуризации, 98

о существовании слабейших

предусловий, 136

о цикле, 103

об удалении подпрограмм, 171

об удалении рекурсии, 174

Тест, 34

простой, 67

Трансляция, 10

Тройка Хоара, 106

УПР, 109

Усиление предусловия, 109

Условие, 105

зацикливания, 45, 48, 85, 86,

161

Форма записи

инфиксная, 20

префиксная, 20

Формула логическая, 28

атомная, 28

Функция, 19

тотальная, 22

частичная, 21

ЦП, 119

ЦЧ, 119

Цепь

убывающая, 24

Цикл, 26

Числа Фибоначчи, 86

Эквивалентность

алгоритмов, 54

формул, 30

Эффективное построение, 92

Язык естественный, 9

Язык программирования, 10

второго уровня, 12

декларативный, 14

императивный, 14

объектно-ориентированного,

первого уровня, 12

с метками, 15

специализированный, 15

структурный, 15

третьего уровня, 12

универсальный

, 10

универсальный

, 14

функционального, 15