Алгоритмы - построение и анализ (1021735), страница 12
Текст из файла (страница 12)
Например, является ли возведение в степень элементарной командой? В общем случае — нет; чтобы вычислить выражение х", в котором х и у — действительные числа, потребуется несколько команд. Однако в некоторых случаях эту операцию можно представить в виде элементарной команды. Во многих компьютерах имеется команда побитового сдвига влево, которая в течение времени, требуемого для выполнения элементарной команды, сдвигает биты целого числа на )с позиций влево.
В большинстве случаев такой сдвиг целого числа на одну позицию эквивалентен его умножению на 2. Сдвиг битов на )с позиций влево эквивалентен его умножению на 2Й. Таким образом, на этих компьютерах 2Й можно вычислить с помощью одной элементарной инструкции, сдвинув целое число 1 на )с позиций влево; при этом Й не должно превышать количество битов компьютерного слова. Мы попытаемся избегать таких "серых областей" модели ВАМ, однако вычисление 2/с будет рассматриваться как элементарная операция, если Й вЂ” достаточно малое целое положительное число.
В исследуемой модели ВАМ не предпринимаются попытки смоделировать иерархию запоминающих устройств, общепринятую на современных компьютерах. Таким образом, кэш и виртуальная память (которая чаще всего реализуется в соответствии с требованиями страничной организации памяти) не моделируется. В некоторых вычислительных моделях предпринимается попытка смоделировать эффекты, вызванные иерархией запоминающих устройств, которые иногда важны в реальных программах, работающих на реальных машинах. В ряде рассмотренных в данной книге задач принимаются во внимание эти эффекты, но в большинстве случаев они не учитываются. Модели, включающие в себя иерархию запоминающих устройств, заметно сложнее модели НАМ, поэтому они могут затруднить работу.
Кроме того, анализ, основанный на модели ВАМ, обычно бб Часть й Основы замечательно предсказывает производительность алгоритмов, выполняющихся на реальных машинах. Анализ даже простого алгоритма в модели ВАМ может потребовать значительных усилий. В число необходимых математических инструментов может войти комбинаторика, теория вероятностей, навыки алгебраических преобразований и способность идентифицировать наиболее важные слагаемые в формуле.
Поскольку поведение алгоритма может различаться для разных наборов входных значений, потребуется методика учета, описывающая поведение алгоритма с помощью простых и понятных формул. Даже когда для анализа данного алгоритма выбирается всего одна модель машины, нам все еще предстоит выбрать средства для выражения анализа. Хотелось бы выбрать простые обозначения, которые позволят легко с ними работать и выявлять важные характеристики требований, предъявляемых алгоритмом к ресурсам, а также избегать сложных деталей.
Анализ алгоритма, работающего ио методу вставок Время работы процедуры 1мзвкт~ом Болт зависит от набора входных значений: для сортировки тысячи чисел требуется больше времени, чем для сортировки трех чисел. Кроме того, время сортировки с помощью этой процедуры может быть разным для последовательностей, состоящих из одного и того же количества элементов, в зависимости от степени упорядоченности этих последовательностей до начала сортировки. В общем случае время работы алгоритма увеличивается с увеличением количества входных данных, поэтому общепринятая практика— представлять время работы программы как функцию, зависящую от количества входных элементов.
Для этого понятия "время работы алгоритма" и "размер входных данных" нужно определить точнее. Наиболее адекватное понятие размера входных данных (шрш з1ге) зависит от рассматриваемой задачи. Во многих задачах, таких как сортировка или дискретные преобразования Фурье, это количество входных элементов, например, размер п сортируемого массива. Для многих других задач, таких как перемножение двух целых чисел, наиболее подходящая мера для измерения размера ввода — общее количество битов, необходимых для представления входных данных в обычных двоичных обозначениях. Иногда размер ввода удобнее описывать с помощью не одного, а двух чисел.
Например, если на вход алгоритма подается граф, размер ввода можно описывать, указывая количество вершин и ребер графа. Для каждой рассматриваемой далее задачи будет указываться способ измерения размера входных данных. Время работы алгоритма для того или иного ввода измеряется в количестве элементарных операций, или "шагов", которые необходимо выполнить.
Здесь удобно ввести понятие шага, чтобы рассуждения были как можно более машинно- Глава 2. Приступаем к изучению 67 1)чвбятю)ч Бокт(А) время ) 1ог 7' — 2 Го 1еидйз(А] с) 2 до йеу — А(3] С2 3 5ь Вставка элемента А[3] в отсортированную последовательность А[1..7 — Ц. О 4 з д — 1 С4 5 тчййе з > О аль А[з] > )сеу С5 6 По А[а+ 1] — А[з] Сб 7 — з — 1 Ст 8 А[а+ 1] — йеу Са количество раз и — 1 и — 1 и — 1 2," 2(г, — 1) х 1=2 (ту 1) и — 1 Время работы алгоритма — зто сумма промежутков времени, необходимых для выполнения каждой входящей в его состав исполняемой инструкции. Если вы- 'Здесь есть некоторые тонкие нюансы. Шаги вычислений, описанные на обычном языке, часто представляют собой разновидности процелур, состояших из нескольких элементарных инструкций.
Например. далее в этой книге может встретиться строка "сортировка точек по координате к". Как вы увидите, эта команда требует больше, чем постоянного количестна времени работы. Заметим также, что команда вызова подпрограммы выполняется в течение фиксированного времени, однако сколько длится выполнение вызванной подпрограммы — это зависит от ее сложности. Таким образом, процесс вызова подпрограммы (передача в нее параметров и т.п. действия) следует отличать от выполнения этой подпрограммы. независимыми.
На данном этапе мы будем исходить из точки зрения, согласно которой для выполнения каждой строки псеводкода требуется фиксированное время. Время выполнения различных строк может отличаться, но мы предположим, что одна и та же з-я строка выполняется за время оп где с, — константа. Эта точка зрения согласуется с моделью ВАМ и отражает особенности практической реализации псевдокода на реальных компьютерах". В последующих рассуждениях формула для выражения времени работы алгоритма 1)сбавят)оы Бокт, которая сначала будет сложным образом зависеть от всех величин с„значительно упростится благодаря более лаконичным обозначениям, с которыми проще работать. Эти более простые обозначения позволят легче определить, какой из двух алгоритмов эффективнее.
Начнем с того, что введем для процедуры 1)чбййт)о)ч Войт время выполнения каждой инструкции и количество их повторений. Для каждого д = 2,3,...,и, где и = 1еидЖ (А], обозначим через г, количество проверок условия в цикле тчЬПе (строка 5). При нормальном завершении циклов аког или чгЬПе (т.е. когда перестает выполняться условие, заданное в заголовке цикла) условие проверяется на один раз больше, чем выполняется тело цикла. Само собой разумеется, мы считаем, что комментарии не являются исполняемыми инструкциями, поэтому они не увеличивают время работы алгоритма: Часть 1.
Основы 68 полнение инструкции длится в течение времени с; и она повторяется в алгоритме гг раз, то ее вклад в полное время работы алгоритма равно снкз Чтобы вычислить время работы алгоритма 1ызектгоы Болт (обозначим его через Т (и)), нужно просуммировать произведения значений, стоящих в столбцах время и кодичеслгво раз, в результате чего получим: Т (гт) = Сггт+ С2 (гг — 1) + С4 (гг — 1) + С5 ~~г ьу+ Сб ~ (ьу — 1)+ 1=2 5=2 п + ст ~ (~у — 1) + са (и - 1) .
3=2 Даже если размер входных данных является фиксированной величиной, время работы алгоритма может зависеть от степени упорядоченности сортируемых величин, которой они обладали до ввода. Например, самый благоприятный случай для алгоритма 1г48ектгоы Зонт — это когда все элементы массива уже отсортированы. Тогда для каждого з = 2, 3,..., и получается, что А [з] < кеу в строке 5, еще когда т равно своему начальному значению т' — 1. Таким образом, при у' = = 2,3,...,и 4 = 1, и время работы алгоритма в самом благоприятном случае вычисляется так: Т (и) = сггз+ с2 (и 1) + с4 (гт 1) + с5 (гт 1) + са (гт 1) = (С1 + С2 + С4 + С5 + С8) Гà — (С2 + С4 + С5 + С8) Это время работы можно записать как агг + б, где а и 6 — константы, зависящие от величин с;; т.е. это время является линейной фуикг4ией от ьь Если элементы массива отсортированы в порядке, обратном требуемому (в данном случае в порядке убывания), то это наихудший случай.
Каждый элемент А [Я необходимо сравнивать со всеми элементами уже отсортированного подмножества А [1.. т' — 1[, так что для з = 2, 3,..., тг значения т = у. С учетом того, что т гг(п+ 1) ,7 э= 3=2 гт (гг — 1) 2 О-1)= 2 3=2 ~Это правило не всегда применимо к такому ресурсу, как память. Если инструкпия оперирует с т словами памяти и выполняется и раз, то это енге не означает, что всего при этом потребляется гии слов памяти. Глава 2.
Приступаем к изучению 69 (как выполняется это суммирование, показано в приложении А), получаем, что время работы алгоритма 1мзнкт|он Зонт в худшем случае определяется соотношением 2 (п) = с1п + сз (п — 1) + С4 (п 1) + с5 /п(п+ 1) 2 -)+ +сб +с7 +са(п — 1) = =( С5 С6 С7~ З / С5 С5 С7 — + — + — ~ и + ~С7 + сз + с4 + — — — — — + са) и— 2 2 2~ 2 2 2 (СЗ + С4 + С5 + С8) . Это время работы можно записать как апз + Ьп+ с, где константы а, Ь и с зависят от с;.
Таким образом, это квадратичная функция от и. Обычно время работы алгоритма фиксировано для определенных входных данных, как в случае сортировки вставкой, однако в последующих главах мы ознакомимся с некоторыми интересными алгоритмами, поведение которых носит вероятностный характер.
Время их работы может меняться даже для одних и тех же входных данных. Наихудшее и среднее время работы Анализируя алгоритм, работающий по методу вставок, мы рассматривали как наилучший, так и наихудший случай, когда элементы массива были рассортированы в порядке, обратном требуемому. Далее в этой книге мы будем уделять основное внимание определению только времени работы в на44худи4ем случае, т.е. максимальном времени работы из всех входных данных размера п. Тому есть три причины. ° Время работы алгоритма в наихудшем случае — это верхний предел этой величины для любых входных данных. Располагая этим значением, мы точно знаем, что для выполнения алгоритма не потребуется большее количество времени.
Не нужно будет делать каких-то сложных предположений о времени работы и надеяться, что на самом деле эта величина не будет превышена. ° В некоторых алгоритмах наихудший случай встречается достаточно часто. Например, если в базе данных происходит поиск информации, то наихудшему случаю соответствует ситуация, когда нужная информация в базе данных отсутствует. В некоторых поисковых приложениях поиск отсутствующей информации может происходить довольно часто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
