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

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

В схемах структур данных мы будем рисовать стрелку из ячейки курсора к ячейке, на которую указывает курсор. Иногда мы также будем показывать целое число в ячейке курсора, напоминая тем самым, что это не настоящий указатель. Читатель может заметить, что механизм указателя Pascal разрешает ячейкам массива только "быть указанными" с помощью курсора, но не быть истинным указателем. Другие языки программирования, подобные PL/1 или С, позволяют компонентам массивов быть истинными указателями и, конечно, "быть указанным" с помощью курсора. В отличие от этих языков, в языках Fortran и Algol, где нет типа указателя, можно использовать только курсоры.

Пример 1.3. На рис. 1.5 показана структура данных, состоящая из двух частей. Она имеет цепочку ячеек, содержащих курсоры для массива reclist (список записей), определенного выще. Назначение поля next (следующий) заключается в указании на следующую запись в массиве reclist. Например, reclist[4].nextравно 1, поэтому запись 4 предществует записи 1. Полагая первой запись 4, в соответствии со значениями поля next получим следующий порядок записей: 4, 1, 3, 2. Отметим, что значение поля next в записи 2, равное О, указывает на то, что нет следующей записи. Целесообразно принять соглащение, что число О будет обозначать нуль-указатель при использовании курсоров и указателей. Но, чтобы не возникали проблемы при реализации этого соглащения, необходимо также условиться, что массивы, на которые указывают курсоры, индексируются начиная с 1, а не с 0.

header


data next reclist

Рис. 1.5. Пример структуры данных

Ячейки в цепочке на рис. 1.5 имеют тип type

recordtype = record cursor: integer; prt: t recordtype

Ha цепочку можно ссылаться с помощью переменной header (заголовок), имеющей тип Т recordtype, header указывает на анонимную запись типа recordtype*.

Запись анонимна (не имеет имени), так как создается с помощью вызова new(header), где header указывает на вновь создаваемую запись. В памяти компьютера, конечно, есть адрес, по которому можно локализовать ячейку с записью.



Эта запись имеет значение 4 в поле cursor. Мы рассматриваем 4 как индекс массива reclist. Эта запись имеет истинный указатель в поле ptr на другую анонимную запись, которая, в свою очередь, указывает на индекс 4 массива reclist и имеет нуль-указатель в поле prt. □

1.4. Время выполнения программ

в процессе рещения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. В самом деле, на чем основывать свой выбор, если алгоритм должен удовлетворять следующим противоречащим друг другу требованиям.

1. Быть простым для понимания, перевода в программный код и отладки.

2. Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.

Если написанная программа должна выполняться только несколько раз, то первое требование наиболее важно. Стоимость рабочего времени программиста обычно значительно превыщает стоимость мащинного времени выполнения программы, поэтому стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если мы имеем дело с задачей, рещение которой требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа должна выполняться многократно. Поэтому, с финансовой точки зрения, более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее, чем более простая программа). Но и в этой ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должна себя вести более сложная программа. При построении сложной программной системы желательно реализовать ее простой прототип, на котором можно провести необходимые измерения и смоделировать ее поведение в целом, прежде чем приступать к разработке окончательного варианта. Таким образом, программисты должны быть осведомлены не только о методах построения быстрых программ, но и знать, когда их следует применить (желательно с минимальными программистскими усилиями).

Измерение времени выполнения программ

На время выполнения программы влияют следующие факторы.

1. Ввод исходной информации в программу.

2. Качество скомпилированного кода исполняемой программы.

3. Мащинные инструкции (естественные и ускоряющие), используемые для выполнения программы.

4. Временная сложность алгоритма соответствующей программы.

Поскольку время выполнения программы зависит от ввода исходных данных, его можно определить как функцию от исходных данных. Но зачастую время выполнения программы зависит не от самих исходных данных, а от их "размера". В этом отнощении хорощим примером являются задачи сортировки, которые мы подробно рассмотрим в главе 8. В задачах сортировки в качестве входных данных выступает

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



список элементов, подлежащих сортировке, а в качестве выходного результата - те же самые элементы, отсортированные в порядке возрастания или убывания. Например, входной список 2, 1,3, 1, 5, 8 будет преобразован в выходной список 1, 1, 2, 3, 5, 8 (в данном случае список отсортирован в порядке возрастания). Естественной мерой объема входной информации для программы сортировки будет число элементов, подлежащих сортировке, или, другими словами, длина входного списка, В общем случае длина входных данных - Подходящая мера объема входной информации, и если не будет оговорено иное, то в качестве меры объема входной информации мы далее будем понимать именно длину входных данных.

Обычно говорят, что время выполнения программы имеет порядок Т{п) от входных данных размера п. Например, некая программа имеет время выполнения Т(п) = сп, где с - константа. Единица измерения Т(п.)точно не определена, но мы будем понимать 7(п.)как количество инструкций, выполняемых на идеализированном коййьЮтере.

Для многих программ время выполнения действительно является функцией входных данных, а не их размфа. В этой ситуации мы определяем Т(п) как время выполнения в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера п. Мы также будем рассматривать Тср(п) как среднее (в статистическом смысле) время выполнения по всем входным данным размера п. Хотя Тср{п)яяля-ется достаточно объективной мерой времени выполнения, но часто, нельзя предполагать (или обосновать) равнозначность всех входных данных. На практике среднее время выполнения найти сложнее, чем наихудшее время выполнения, так как- математически это трудноразрещимая задача и, кроме того, зачастую не имеет простого определения понятие "средних" входных данных. Поэтому в основном мы будем использовать наи-худщее время выполнения как меру временной сложности алгоритмов, но не будем забывать и о среднем времени выполнения там, где это возможно,

Теперь сделаем замечание о втором и третьем факторах, влияющих на время выполнения программ: о компиляторе, используемом для компиляции программы, и мащине, на которой выполняется программа. Эти факторы влияют на то, что для измерения времени выполнения Т(п) мы не можем применить стандартные единицы измерения, такие как секунды или миллисекунды. Поэтому мы можем только делать заключения, подобные "время выполнения такого-то алгоритма пропорционально п". Константы пропорциональности также нельзя точно определить, поскольку они зависят от компилятора, компьютера и других факторов.

Асимптотические соотношения

Для описания скорости роста функций используется 0-симв6лика. Например, когда мы говорим, что время выполнения Т(п) некоторой программы имеет порядок О(ге) (читается "о-большое от га в квадрате" или просто "о от « в квадрате"), то подразумевается, что существуют Положительные константы с и Ло такие, что для всех га, больщих или равных га,,, выполняется неравенство Т(п)< сп.

Пример 1.4. Предположим, что Т(0) = 1, (l) = 4 и в общем случае Г(п) = (га -Ь \f. Тогда Т(га) имеет порядок О(л): если положить га„ = 1 и с = 4, то легко показать, что для га > 1 будет выполняться неравенство (п + \ f < 4.п. Отметим, что нельзя положить га„ = О, так как Т(0)= 1 и, следовательно, это значение при любой константе с больще сО = 0. П ,

Подчеркнем: мы предполагаем, что все функции времени выполнения определены на множестве неотрицательных целых чисел и их значения также неотрицательны, но необязательно целые. Будем говорить, что Т(га) имеет порядок 0(Лп.)),если существуют константы с и По такие, что для всех л > га„ выполняется неравенство Т(п)< с/(га).Для программ, у которых время выполнения имеет порядок 0(f(n)), говорят, что они имеют порядок (или степень) роста f(n).

Пример 1.5. Функция Т(п) = Зл + 2п имеет степень роста 0(п.). Чтобы это показать, надо положить га„ = О и с = 5, так как легко видеть, что для всех целых я > О выполняется неравенство Зп. + 2п < ЬгР. Можно, конечно, сказать, Что Т[п) имеет Порядок 0(п), но это более слабое утверждение, чем то, что Т(п) имеет порядок роста 0(п.).





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.0038