Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 12
Текст из файла (страница 12)
трактуется как указатель на данные, представляющие этот массив или объект. Для всех полей у" объекта х присваивание у ь- х приводит к тому, что у [у] = 7" [х]. Более того, если теперь выполнить присваивание 7" [х] — 3, 'Инструкннн, зквнвалентные перечнсленным, есть в болынннстве языков программирования с блочной структурой, однако нк синтаксис может немного отлнчатьсв от синтаксиса языка Разсай Глава 2. Приступаем к изучению 63 то впоследствии будет выполняться не только соотношение г (х) = 3, но и соотношение г (у) = 3.
Другими словами, после присваивания у — х переменные х и у указывают на один и тот же объект. Иногда указатель вообще не ссылается ни на какой объект. В таком случае он имеет специальное значение нц.. 8. Параметры передаются в процедуру ло значению: в вызывающей процедуре создается своя собственная копия параметров, и если в вызванной процедуре какому-то параметру присваивается значение, то в вызывающей процедуре не происходит никаких изменений. Если передаются объекты, то происходит копирование указателя на данные, представляющие этот объект, но поля объекта не копируются.
Например, если х — параметр вызванной процедуры, то присваивание х — у, выполненное в этой процедуре, невидимо для вызывающей процедуры. Однако присваивание г )х) - 3 будет видимым. 9. Логические операторы "и" и "или" вычисляются сокращенно (зЬоп с1гсцйшй). Это означает, что при вычислении выражения "х и у" сначала вычисляется значение выражения х. Если оно ложно, то все выражение не может быть истинным, и значение выражения у не вычисляется. Если же выражение х истинно, то для определения значения всего выражения необходимо вычислить выражение у. Аналогично, в выражении "х или у" величина у вычисляется только в том случае, если выражение х ложно. Сокращенные операторы позволяют составлять такие логические выражения, как "х ф мп.
и г" )х] = у", не беспокоясь о том, что произойдет при попытке вычислить выражение г (х), если х = мц.. Упражнения 2.1-1. Используя в качестве модели рис. 2.2, проиллюстрируйте работу алгоритма 1ыкктю1ч Бокт по упорядочению массива А = (31, 41, 59, 26, 41, 58). 2.1-2. Перепишите процедуру 1мзектюм Бокт так, чтобы она выполняла сортировку не в невозрастающем, а в неубывающем порядке. 2.1-3. Рассмотрим задачу поиска. Вход: последовательность и чисел А = (ам аз,...,о ) и величина и.
Выход: индекс з, обладающий свойством о = А [з], или значение ьл[., если в массиве А отсутствует значение о. Составьте псевдокод лилейного поиска, при работе которого выполняется сканирование последовательности в поиске значения е. Докажите корректность алгоритма с помощью инварианта цикла. Убедитесь, что 64 Часть 1. Основы выбранные инварианты цикла удовлетворяют трем необходимым условиям.
2.1-4. Рассмотрим задачу сложения двух двоичных целых чисел длиной и битов каждое, хранящихся в массивах А и В, которые состоят из п элементов. Сумму этих двух чисел необходимо занести в двоичной форме в массив С, состоящий из и + 1 элемента. Приведите строгую формулировку задачи и составьте псевдокод для сложения этих двух чисел. 2.2 Анализ алгоритмов Анализ алгоритма заключается в том, чтобы предсказать требуемые для его выполнения ресурсы.
Иногда оценивается потребность в таких ресурсах, как память, пропускная способность сети или необходимое аппаратное обеспечение, но чаще всего определяется время вычисления. Путем анализа нескольких алгоритмов, предназначенных для решения одной и той же задачи, можно без труда выбрать наиболее эффективный. В процессе такого анализа может также оказаться, что несколько алгоритмов примерно равноценны, а все остальные нужно отбросить. Прежде чем мы научимся анализировать алгоритмы, необходимо разработать технологию, которая будет для этого использоваться. В эту технологию нужно будет включить модель ресурсов и величины их измерения.
С учетом того, что алгоритмы реализуются в виде компьютерных программ, в этой книге в большинстве случаев в качестве технологии реализации принята модель обобщенной однопроцессорной машины с памятью с лроизвольным достуном (йапдош-Ассезз Мас)ппе — ВАМ). В этой модели команды процессора выполняются последовательно; одновременно выполняемые операции отсутствуют. Строго говоря, в модели ВАМ следует точно определить набор инструкций и время их выполнения, однако это утомительно и мало способствует пониманию принципов разработки и анализа алгоритмов. С другой стороны, нужно соблюдать осторожность, чтобы не исказить модель ВАМ.
Например, что будет, если в ВАМ встроена команда сортировки? В этом случае сортировку можно выполнять с помощью всего одной команды процессора. Такая модель нереалистична, поскольку настоящие компьютеры не имеют подобных встроенных команд, а мы ориентируемся именно на их устройство. В рассматриваемую модель входят те команды, которые обычно можно найти в реальных компьютерах: арифметические (сложение, вычитание, умножение, деление, вычисление остатка деления, приближение действительного числа ближайшим меньшим или ближайшим большим целым), операции перемещения данных (загрузка, занесение в память, копирование) и управляющие (условное и безусловное ветвление, вызов подпрограммы и воз- Глава 2.
Приступаем к изучению 65 врат из нее). Для выполнения каждой такой инструкции требуется определенный фиксированный промежуток времени. В модели ВАМ есть целочисленный тип данных и тип чисел с плавающей точкой. Несмотря на то, что обычно в этой книге точность не рассматривается, в некоторых приложениях она играет важную роль. Также предполагается, что существует верхний предел размера слова данных. Например, если обрабатываются входные данные с максимальным значением п, обычно предполагается, что целые числа представлены с1кп битами, где с — некоторая константа, не меньшая единицы. Требование с > 1 обусловлено тем, что в каждом слове должно храниться одно из п значений, что позволит индексировать входные элементы.
Кроме того, предполагается, что с — это конечная константа, поэтому объем слова не может увеличиваться до бесконечности. (Если бы это было возможно, в одном слове можно было бы хранить данные огромных объемов и осуществлять над ними операции в рамках одной элементарной команды, что нереально.) В реальных компьютерах содержатся команды, не упомянутые выше, которые представляют "серую область" модели ВАМ. Например, является ли возведение в степень элементарной командой? В общем случае — нет; чтобы вычислить выражение х", в котором х и у — действительные числа, потребуется несколько команд.
Однако в некоторых случаях эту операцию можно представить в виде элементарной команды. Во многих компьютерах имеется команда побитового сдвига влево, которая в течение времени, требуемого для выполнения элементарной команды, сдвигает биты целого числа на )с позиций влево. В большинстве случаев такой сдвиг целого числа на одну позицию эквивалентен его умножению на 2.
Сдвиг битов на )с позиций влево эквивалентен его умножению на 2Й. Таким образом, на этих компьютерах 2Й можно вычислить с помощью одной элементарной инструкции, сдвинув целое число 1 на Й позиций влево; при этом Й не должно превышать количество битов компьютерного слова. Мы попытаемся избегать таких "серых областей" модели ВАМ, однако вычисление 2/с будет рассматриваться как элементарная операция, если Й вЂ” достаточно малое целое положительное число.
В исследуемой модели ВАМ не предпринимаются попытки смоделировать иерархию запоминающих устройств, общепринятую на современных компьютерах. Таким образом, кэш и виртуальная память (которая чаще всего реализуется в соответствии с требованиями страничной организации памяти) не моделируется. В некоторых вычислительных моделях предпринимается попытка смоделировать эффекты, вызванные иерархией запоминающих устройств, которые иногда важны в реальных программах, работающих на реальных машинах.
В ряде рассмотренных в данной книге задач принимаются во внимание эти эффекты, но в большинстве случаев они не учитываются. Модели, включающие в себя иерархию запоминающих устройств, заметно сложнее модели НАМ, поэтому они могут затруднить работу. Кроме того, анализ, основанный на модели ВАМ, обычно бб Часть й Основы замечательно предсказывает производительность алгоритмов, выполняющихся на реальных машинах. Анализ даже простого алгоритма в модели ВАМ может потребовать значительных усилий. В число необходимых математических инструментов может войти комбинаторика, теория вероятностей, навыки алгебраических преобразований и способность идентифицировать наиболее важные слагаемые в формуле. Поскольку поведение алгоритма может различаться для разных наборов входных значений, потребуется методика учета, описывающая поведение алгоритма с помощью простых и понятных формул.
Даже когда для анализа данного алгоритма выбирается всего одна модель машины, нам все еще предстоит выбрать средства для выражения анализа. Хотелось бы выбрать простые обозначения, которые позволят легко с ними работать и выявлять важные характеристики требований, предъявляемых алгоритмом к ресурсам, а также избегать сложных деталей. Анализ алгоритма, работающего ио методу вставок Время работы процедуры 1мзвкт~ом Болт зависит от набора входных значений: для сортировки тысячи чисел требуется больше времени, чем для сортировки трех чисел. Кроме того, время сортировки с помощью этой процедуры может быть разным для последовательностей, состоящих из одного и того же количества элементов, в зависимости от степени упорядоченности этих последовательностей до начала сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
