Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[3]

тов копируется указатель на данные, составляющие этот объект, а сами поля объекта - нет. Например, если х - параметр процедуры, то присваивание х <- у, выполненное внутри процедуры, снаружи заметить нельзя, а присваивание f[x] <- 3 - можно.

Упражнения

1.1-1 Следуя образцу рис. 1.2, покажите, как работает Insertion-Sort на входе А = (31,41, 59, 26,41,58).

1.1-2 Измените процедуру Insertion-Sort так, чтобы она сортировала числа в невозрастающем порядке (вместо неубывающего).

1.1-3 Рассмотрим следующую задачу поиска:

Вход: Последовательность га чисел А = (а\, ci2, ., ап) и число v.

Выход: Индекс г, для которого v = A[i], или специальное значение nil, если v не встречается в А.

Напишите программу линейного поиска (linear search), который последовательно просматривает А в поисках v.

1.1-4 Даны два га-значных двоичных числа, записанных в виде га-элементных массивов А и В. Требуется поместить их сумму (в двоичной записи) в (га+ 1)-элементный массив С. Уточните постановку задачи и запишите соответствующую программу на псевдокоде.

1.2. Анализ алгоритмов

Рассматривая различные алгоритмы решения одной и той же задачи, полезно проанализировать, сколько вычислительных ресурсов они требуют (время выполнения, память), и выбрать наиболее эффективный. Конечно, надо договориться о том, какая модель вычислений используется. В этой книге в качестве модели по большей части используется обычная однопроцессорная машина с произвольным доступом (random-access machine, RAM), не предусматривающая параллельного выполнения операций. (Мы рассмотрим некоторые модели параллельных вычислений в последней части книги.)

Сортировка вставками: анализ

Время сортировки вставками зависит от размера сортируемого массива: чем больше массив, тем больше может потребоваться


времени. Обычно изучают зависимости времени работы от размера входа. (Впрочем, для алгоритма сортировки вставками важен не только размер массива, но и порядок его элементов: если массив почти упорядочен, то времени требуется меньше.)

Как измерять размер входа (input size)? Это зависит от конкретной задачи. В одних случаях разумно считать число элементов на входе (сортировка, преобразование Фурье). В других более естественно считать общее число битов, необходимое для представления всех входных данных. Иногда размер входа измеряется не одним числом, а несколькими (например, число вершин и число рёбер графа).

Временем работы (running time) алгоритма мы называем число элементарных шагов, которые он выполняет - вопрос только в том, что считать элементарным шагом. Мы будем полагать, что одна строка псевдокода требует не более чем фиксированного числа операций (если только это не словесное описание какой-то сложной операции - типа «отсортировать все точки по ж-координате»). Мы будем различать также вызов (call) процедуры (на который уходит фиксированное число операций) и её исполнение (execution), которое может быть долгим.

Итак, вернёмся к процедуре Insertion-Sort и отметим около каждой строки её стоимость (число операций) и число раз, которое эта строка исполняется. Для каждого j от 2 до га (здесь га = length[A] - размер массива) подсчитаем, сколько раз будет исполнена строка 5, и обозначим это число через tj. (Заметим, что строки внутри цикла выполняются на один раз меньше, чем проверка, поскольку последняя проверка выводит из цикла.)

Insertion-Sort(A)стоимость число раз

1

for j <- 2 to length[A]

Cl

ra

2

do key <- A[j]

C2

ra -

1

3

> добавить A[j] к отсортиро-

> ванной части A[l. .j - 1].

0

ra -

1

4

г <r- j - 1

c4

ra -

1

5

while г > 0 and A[i] > key

C5

£"=

= 2 *j

6

do A[i + A[i]

Сб

£"=

=2&-!

7

i <- i - 1

C7

£"=

8

A[i +l]<r- key

C8

ra -

1

Строка стоимости с, повторённая т раз, даёт вклад cm в общее число операций. (Для количества использованной памяти этого


сказать нельзя!) Сложив вклады всех строк, получим

п

Т(п) = cin + с2(га - 1) + с4(га - 1) + с5+

J = 2

п

п

+ се J>j " !) + с7J>j - 1) + с8(п - 1).

j = 2j = 2

Как мы уже говорили, время работы процедуры зависит не только от га, но и от того, какой именно массив размера га подан ей на вход. Для процедуры Insertion-Sort наиболее благоприятен случай, когда массив уже отсортирован. Тогда цикл в строке 5 завершается после первой же проверки (поскольку A[i] key при г = j - 1), так что все tj равны 1, и общее время есть

Г(га) = сгп + с2(га - 1) + с4(га - 1) + с5(га - 1) + с8(га - 1) =

= (ci + с2 + с4 + с5 + с8)га - (с2 + с4 + с5 + с8).

Таким образом, в наиболее благоприятном случае время Т(п), необходимое для обработки массива размера га, является линейной функцией (linear function) от га, т.е. имеет вид Т{п) = an + Ь для некоторых констант а и Ь. (Эти константы определяются выбранными значениями с\,..., с8.)

Если же массив расположен в обратном (убывающем) порядке, время работы процедуры будет максимальным: каждый элемент A[j] придётся сравнить со всеми элементами А[1] .. .A[j - 1]. При этом tj = j. Вспоминая, что

(см. гл. 3), получаем, что в худшем случае время работы процедуры равно

Теперь функция Т(п) - квадратичная (quadratic function), т.е. имеет вид Т(п) = an2 + Ъп + с. (Константы а, Ъ и с снова определяются значениями ci-c8.)

- (с2 + с4 + с5 + с8)



[стр.Начало] [стр.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] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]