Для решения одной и той же задачи можно разработать несколько разных алгоритмов. Поэтому возникает задача выбора наиболее эффективных алгоритмов. Заметим, что точная оценка эффективности алгоритмов очень сложная задача и в каждом конкретном случае требует проведения специального исследования .

Ту часть теории алгоритмов, которая занимается оценкой характеристик алгоритмов, называют метрической. Ее можно разделить на дескриптивную (качественную) и метрическую (количественную) . Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими «вычислений», т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе алгоритм А будет сложнее В , а при другом способе - наоборот.

Чаще всего алгоритмы оцениваются по требуемой памяти, числу выполняемых операций, времени решения или погрешности вычислений. Эти характеристики зачастую зависят от параметров (размерности) задачи и имеют нелинейный характер. Поэтому в теории алгоритмов существует направление оценки эффективности алгоритмов по асимптотическим оценкам функций: требуемой памяти, времени вычисления и т.п. При этом определяется наиболее существенный параметр функции и исследуется поведение функции при возрастании значений параметра. В ходе исследования пытаются определить, какой характер носит зависимость значений рассматриваемой характеристики алгоритма от параметра. Она может быть линейной (т.е. пропорциональной параметру n), логарифмической (т.е. пропорциональной log n), квадратичной (т.е. пропорциональной n 2) и т.д. Сравнивая асимптотические оценки алгоритмов, решающих одну и ту же задачу, можно выбрать более эффективный алгоритм. Говорят, что значение некоторого параметра T(n) имеет порядок n x , если существуют такие положительные константы k и n o , что для всех n³n o , выполняется неравенство T(n) ≤ k n x .

Предположим, что n – количество числовых данных, поступающих на вход нескольких разных алгоритмов (А 1 , А 2 , А 3 , А 4 , А 5), которые производят вычисления с одинаковой скоростью - 1000 операций в секунду, но имеют разные асимптотические оценки. В табл.1.8 показаны значения n, которые могут обработать эти алгоритмы в 1 секунду, 1 минуту и 1 час (значения округлены в меньшую сторону до целого числа). Данные табл.1.3 наглядно показывают, что производительность алгоритма (т.е. число данных, обрабатываемых в единицу времени) существенно зависит от характера функции асимптотической оценки.

Тестирование разработанных алгоритмов обычно проводится при небольших значениях параметра n. Такое тестирование позволяет получить уверенность в работоспособности алгоритма, но вовсе не гарантирует выполнение задачи при больших значениях n. Нам может просто не хватить памяти ЭВМ или времени для решения реальной задачи. Асимптотические оценки важны в том смысле, что позволяют оценить достаточность ресурсов ЭВМ для практических вычислений при известных пределах изменения параметра n.

Главные принципы создания эффективных алгоритмов

Каждый, кто занимается разработкой алгоритмов, должен овладеть некоторыми основными методами и понятиями. Перед тем, кто когда-то столкнулся с трудной задачей, вставал вопрос: «С чего начать?» Один из возможных путей - просмотреть свой запас общих алгоритмических методов, чтобы проверить, нельзя ли с помощью одного из них сформулировать решение новой задачи. Ну а если такого запаса нет, то как все-таки разработать хороший алгоритм? С чего начать? У всех есть печальный опыт, когда смотришь на задачу и не знаешь, что делать. Рассмотрим три общих метода решения задач, полезных для разработки алгоритмов.

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

• 1. Можно ли решить часть задачи? Можно ли, игнорируя некоторые условия, решить оставшуюся часть задачи?
• 2. Можно ли решить задачу для частных случаев? Можно ли разработать алгоритм, который дает решение, удовлетворяющее всем условиям задачи, но входные данные которого ограничены некоторым подмножеством всех входных данных?
• 3. Есть ли что-то, относящееся к задаче, что недостаточно хорошо уяснено? Если попытаться глубже вникнуть в некоторые особенности задачи, удастся ли узнать нечто, что поможет подойти к решению?
• 4. Известно ли решение похожей задачи? Можно ли видоизменить ее решение для решения рассматриваемой задачи? Возможно ли, что эта задача эквивалентна известной нерешенной задаче?

Второй метод разработки алгоритмов известен как метод подъема. Алгоритм подъема начинается с принятия начального предположения или вычисления начального решения задачи. Затем начинается максимально возможное быстрое движение «вверх» от начального решения по направлению к лучшим решениям. Когда алгоритм достигнет такой точки, из которой больше невозможно двигаться наверх, алгоритм останавливается. К сожалению, не всегда можно гарантировать, что окончательное решение, полученное с помощью алгоритма подъема, оптимальное. Эта ситуация часто ограничивает применение метода подъема.

Вообще методы подъема относятся к «грубым». Они запоминают некоторую цель и стараются сделать все что могут и где могут, чтобы подойти ближе к цели. Это делает их несколько «недальновидными». Недальновидность метода подъема хорошо иллюстрируется следующим примером. Пусть требуется найти максимум функции у =/(х), представленной графиком (рис. 2.15). Если начальное значение аргумента х = а, то метод подъема даст устремление к ближайшей цели, т.е. к значению функции в точке х = Ь, тогда как подлинный максимум этой функции находится вх = с. В данном случае

Рис. 2.15. Иллюстрация метода подъема метод подъема находит локальный максимум, но не глобальный. В этом и состоит «грубость» метода подъема.

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

Рассмотрим все три метода в задаче о джипе. Пусть требуется пересечь на джипе 1000-километровую пустыню, израсходовав при этом минимум горючего. Объем топливного бака джипа 500 л, горючее расходуются равномерно, по 1 л на 1 км. При этом в точке старта имеется неограниченный резервуар с топливом. Поскольку в пустыне нет складов с горючим, необходимо установить свои собственные хранилища и наполнять их топливом из бака машины. Итак, идея задачи ясна: нужно из точки старта отъезжать с полным баком на некоторое расстояние, устраивать там первый склад, оставлять там какое-то количество горючего из бака, но такое, чтобы хватило вернуться назад. В точке старта вновь производится полная заправка и делается попытка второй склад продвинуть в пустыню дальше. Но где обустраивать эти склады и сколько горючего оставлять в каждом из них?

Подойдем к решению этой задачи с помощью метода отрабатывания назад. С какого расстояния от конца можно пересечь пустыню, имея запас горючего в точности к баков? Рассмотрим этот вопрос для к = 1,2, 3,... пока не найдем такое целое п, что п полных баков позволяет пересечь всю 1000-километровую пустыню. Для к = 1 ответ равен 500 км = 500 л (точка В), как показано на рис. 2.16.

Рис. 2.16.

Можно заправить машину в точке В и пересечь оставшиеся 500 км пустыни. Была поставлена частная цель, потому что нельзя решить сразу исходную задачу.

Предположим, что к = 2, т.е. есть два полных бака (1000 л). Эта ситуация иллюстрируется на рис. 2.16. Каково максимальное значение jCj, такое, что, отправляясь с 1000 л горючего из точки (500 - Xj), можно перевезти достаточно горючего в точку, чтобы завершить поездку, как в случае к = 1. Один из способов определения приемлемого значения х { состоит в следующем. Заправляемся в точке (500 - Xj), едем х { километров до точки В и переливаем в хранилище все горючее, кроме той части, которая потребуется для возвращения в точку (500 - Xj). В этой точке бак становится пустым. Теперь наполняем второй бак, проезжаем Xj километров до В , забираем в В горючее, оставленное там, и из В едем в С с полным баком. Общее пройденное расстояние состоит из трех отрезков по х { километров и одного отрезка ВС длиной 500 км. Поэтому находим из уравнения 3x t + 500 = = 1000 его решение Xj = 500/3. Таким образом, два бака (1000 л) позволяют проехать Z> 2 = 500 +х { = 500(1 + 1/3) км.

Рассмотрим к = 3. Из какой точки можно выехать с 1500 л топлива так, что джип сможет доставить 1000 л в точку (500 - х })? Найдем наибольшее значение х 2 , такое, что, выезжая с 1500 л топлива из точки (500 - Xj - х 2), можно доставить 1000 л в точку (500 - Xj). Выезжаем из точки (500 - Xj - х 2), доезжаем до (500 - х,), переливаем все горючее, кроме х 2 литров, и возвращаемся в точку (500 - Xj - х 2) с пустым баком. Повторив эту процедуру, затратим 4х 2 литров на проезд и оставим (1000 - 4х 2) литров в точке (500 - x L). Теперь в точке (500 - Xj - х 2) осталось ровно 500 л. Заправляемся последними 500 л и едем в точку (500 - Xj), израсходовав на это х 2 литров.

Находясь в точке (500 - Xj), на проезд затрачиваем 5х 2 литров топлива. Здесь оставлено в общей сложности (1500 - 5х 2) литров. Это количество должно быть равно 1000 л, т.е. х 2 = 500/5. Из этого заключаем, что 1500 л позволяют проехать

Продолжая индуктивно процесс отрабатывания назад, получаем, что п баков горючего позволяют нам проехать D n километров, где D n = 500(1 +1/3 + 1/5 + ... + 1/(2п - 1)).

Нужно найти наименьшее значение п, при котором D n > 1000. Простые вычисления показывают, что для п = 7 имеем D ? = 997,5 км, т.е. семь баков, или 3500 л, топлива дадут возможность проехать

• 977.5 км. Полный восьмой бак - это было бы уже больше необходимого, чтобы перевезти 3500 л из точки А в точку, отстоящую на
• 22.5 км (1000 - 977,5) от А Читателю предоставляется возможность самостоятельно убедиться в том, что для доставки 3500 л топлива к отметке 22,5 км достаточно 337,5 л. Таким образом, для того чтобы пересечь на машине пустыню из И в С, нужно 3837,5 л горючего.

Теперь алгоритм транспортировки топлива может быть представлен следующим образом. Стартуем из А, имея 3837,5 л. Здесь как раз достаточно топлива, чтобы постепенно перевезти 3500 л к отметке

22.5 км, где джип в конце концов окажется с пустым баком и запасом топлива на 7 полных заправок. Этого топлива достаточно, чтобы перевезти 3000 л к точке, отстоящей на 22,5 + 500/13 км от А, где бак машины будет опять пуст. Последующие перевозки приведут джип к точке, отстоящей на 22,5 + 500/13 + 500/11 км от А, с пустым баком машины и 2500 л на складе.

Продолжая таким образом, мы продвигаемся вперед благодаря анализу, проведенному методом отрабатывания назад. Вскоре джип окажется у отметки 500(1 - 1/3) км с 1000 л топлива. Затем перевезем 500 л топлива в точку В, зальем их в бак машины и доедем без остановки до точки С (рис. 2.17).

Рис. 2.17.

Для тех, кто знаком с бесконечными рядами, заметим, что D есть п -ная частная сумма нечетного гармонического ряда. Поскольку этот ряд расходится, алгоритм дает возможность пересечь любую пустыню. Попробуйте модифицировать этот алгоритм для того, чтобы оставить достаточно топлива в различных точках пустыни для возвращения в точку А.

Возникает вопрос, можно ли проехать 1000 км, затратив меньше чем 3837,5 л топлива. Оказывается, нельзя. Доказательство этого утверждения довольно сложное. Однако можно высказать следующий, довольно правдоподобный довод. Очевидно, мы действуем наилучшим образом для к = 1. При к = 2 используется план для к = 1 и затем вводится в действие второй бак топлива для того, чтобы оказаться как можно дальше от точки В. Исходная предпосылка для к баков состоит в том, что мы знаем, как действовать наилучшим образом в случае с (к - 1) баками, и отодвигаемся как можно дальше назад с помощью к-то бака.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ

• 1. Дайте определение объекта, класса, системы, модели.
• 2. Назовите основные типы моделей.
• 3. Что такое имитационное моделирование?
• 4. Какие классификации моделей существуют?
• 5. Укажите основные этапы моделирования.
• 6. Что такое алгоритм?
• 7. Перечислите свойства алгоритма.
• 8. Какие этапы выполняются при полном построении алгоритма?
• 9. Что такое блок-схема алгоритма?
• 10. Дайте определение функционального блока.
• 11. Какой алгоритм называется структурным?
• 12. Назовите главные принципы, лежащие в основе создания эффективных алгоритмов.

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

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

Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы , оптимизирующий компилятор , оптимизация циклов , оптимизатор объектного кода , и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».

История вопроса

Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа :

«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь - выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления» .

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

Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:

«В установившихся технических дисциплинах улучшение на 12 % легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании»

Обзор

Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.

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

Существует много путей измерения используемых алгоритмом ресурсов. Два наиболее используемых измерения - скорость и используемая память. Другие измерения могут включать скорость передачи, временное использование диска, долговременное использование диска, потребление энергии, совокупная стоимость владения , время отклика на внешние сигналы и так далее. Многие из этих измерений зависят от размера входных данных алгоритма (то есть от количеств, требующих обработки данных). Измерения могут также зависеть от способа, в котором данные представлены (например, некоторые алгоритмы сортировки плохо работают на уже сортированных данных или когда данные отсортированы в обратном порядке).

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

Теоретический анализ

В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое . Эта оценка, в основном, достаточно точна при большом n , но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).

Обозначение	Название	Примеры
O (1) {\displaystyle O(1)\,}	постоянное	Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хеш-функции для выбора элемента.
O (log ⁡ n) {\displaystyle O(\log n)\,}	логарифмическое	Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева , как и операции в биномиальной куче .
O (n) {\displaystyle O(n)\,}	линейное	Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n -битных чисел с использованием сквозного переноса .
O (n log ⁡ n) {\displaystyle O(n\log n)\,}	квазилинейное , логарифмически линейное	Вычисление быстрого преобразования Фурье , пирамидальная сортировка , быстрая сортировка (лучший и средний случай), сортировка слиянием
O (n 2) {\displaystyle O(n^{2})\,}	квадратное	Умножение двух n -значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла , быстрая сортировка (худший случай), сортировка выбором , сортировка вставками
O (c n) , c > 1 {\displaystyle O(c^{n}),\;c>1}	экспоненциальное	Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования . Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора

Проверочные испытания: измерение производительности

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

Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как, например, Roy Longbottom’s PC Benchmark Collection , а The Computer Language Benchmarks Game сравнивает производительность реализаций типичных задач в некоторых языках программирования.

Вопросы реализации

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

Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадают выравнивание данных , детализация , сборка мусора , параллелизм на уровне команд и вызов подпрограмм .

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

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

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

Измерения обычно выражаются как функция от размера входа n .

Два наиболее важных измерения:

• Время : как долго алгоритм занимает процессор.
• Память : как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.

Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:

• Прямое потребление энергии : энергия, необходимая для работы компьютера.
• Косвенное потребление энергии : энергия, необходимая для охлаждения, освещения, и т. п.

В некоторых случаях нужны другие, менее распространённые измерения:

• Размер передачи : пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие . Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
• Внешняя память : память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
• Время отклика : параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
• Общая стоимость владения : параметр важен, когда предназначен для выполнения одного алгоритма.

Время

Теория

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

Память

Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма , чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое .

Существует четыре аспекта использования памяти:

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

Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.

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

• Кэш (часто, статическая RAM) - работает на скоростях, сравнимых с ЦПУ
• Основная физическая память (часто, динамическая RAM) - работает чуть медленнее ЦПУ
• Виртуальная память (зачастую, на диске) - даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.

Алгоритм, необходимая память которого укладывается в кэш компьютера, работает много быстрее, чем алгоритм, умещающийся в основную память, который, в свою очередь, будет много быстрее алгоритма, который использует виртуальное пространство. Усложняет ситуацию факт, что некоторые системы имеют до трёх уровней кэша. Различные системы имеют различное количество этих типов памяти, так что эффект памяти для алгоритма может существенно отличаться при переходе от одной системы к другой.

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

Примеры эффективных алгоритмов

Критика текущего состояния программирования

Программы становятся медленнее более стремительно, чем компьютеры становятся быстрее.

Мэй утверждает:

В широко распространённых системах уменьшение вдвое выполнение команд может удвоить жизнь батареи, а большие данные дают возможность для лучших алгоритмов: Уменьшение числа операций с N x N до N x log(N) имеет сильный эффект при больших N … Для N=30 миллиарда, эти изменения аналогичны 50 годам технологических улучшений.

Соревнования за лучший алгоритм

Следующие соревнования приглашают принять участие в разработке лучших алгоритмов, критерий качества которых определяют судьи:

См. также

• Арифметическое кодирование - вид энтропийного кодирования с переменной длиной кода для эффективного сжатия данных
• Ассоциативный массив - структура данных, которую можно сделать более эффективной при применении деревьев PATRICIA или массивов Джуди
• Тест производительности - метод измерения сравнительного времени исполнения в определённых случаях
• Наилучший, наихудший и средний случай - соглашения по оценке времени выполнения по трём сценариям
• Двоичный поиск - простая и эффективная техника поиска в отсортированном списке
• Таблица ветвления

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

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

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

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

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

Таким образом, будем различать временную T (n ) и пространственную (её также называют ёмкостной) V (n ) сложности алгоритма. При рассмотрении оценок сложности, будем использовать только временную сложность. Пространственная сложность оценивается аналогично.

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

1) временна я сложность алгоритма программы;

2) качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор;

3) внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы);

4) машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных.

Наличие трех последних факторов не позволяет применять типовые единицы измерения временно й сложности алгоритма (секунды, миллисекунды и т.п.), так как можно получить самые различные оценки для одного и того же алгоритма, если использовать труд разных программистов (которые реализуют алгоритм каждый по-своему), разные компиляторы, операционные системы и разные вычислительные машины.

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

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

Часто, временная сложность алгоритма зависит от количества входных данных. Обычно говорят, что временная сложность алгоритма имеет порядок T (n ) от входных данных размера n . Точно определить величину T (n ) на практике представляется довольно трудно. Поэтому прибегают к асимптотическим отношениям с использованием O -символики, которая дает приемлемую оценку времени выполнения алгоритма для не бесконечно больших и не бесконечно малых значений n . Она также позволяет ответить на вопросы наподобие: «во сколько раз быстрее будет работать реализация данного алгоритма на компьютере, быстродействие которого больше нашего, например, в 10 раз»? Казалось бы, ответ очевиден - в 10 раз. Однако, если O (n ) = n (n + 1)/2, то это далеко не так. Или: «насколько дольше будет выполняться программа, если удвоить размер входных данных»? Ответ будет такой: приблизительно в четыре раза медленнее.

Когда используют обозначение «O (×)», имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O (n 2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов.

Например, если число тактов (действий), необходимое для работы алгоритма, выражается как 25n 2 – 10n *log n + 5n + 15, то это алгоритм, для которого T (n ) имеет порядок O (n 2). Фактически, из всех слагаемых оставляется только то, которое вносит наибольший вклад при больших n (в этом случае остальными слагаемыми можно пренебречь), и игнорируется коэффициент перед ним.

Говоря нестрого, обозначение – это множество всех функций, порядок роста которых при достаточно больших n не превышает (т.е. меньше или равен) некоторую константу, умноженную на значение функции .

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

1. максимальную сложность T max (n ), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего;

2. среднюю сложность T mid (n ) – сложность алгоритма в среднем;

3. минимальную сложность T min (n ) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего.

Конец работы -

Эта тема принадлежит разделу:

Министерство образования Российской Федерации

Асимптотические обозначения асимптотически точная оценка функции.. основные классы эффективности.. в теории анализа эффективности алгоритмов к одному классу относят все функции чей порядок роста одинаков с точностью..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Итак, рассмотрены различные варианты вычислительных машин от простейшей машин Тьюринга до однородной вычислительной среды. Все они могут быть использованы для решения тех задач, для которых существует алгоритм. На основе этих моделей строятся более специализированные модели вычислений, а именно: неветвящиеся арифметические программы, битовые вычисления, вычисления с двоичными векторами и деревья решений.

Алгоритмы имеют следующие характеристики:

а) сложность;

б) трудоемкость;

в) надежность, и др.

Для оценки сложности алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении количества входных данных. Свяжем с каждой конкретной задачей некоторое число, называемое ее размером . Например, размером задачи умножения матрицы может быть наибольший размер матриц - сомножителей; размером задачи на графе может быть число ребер данного графа, и т.п.

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

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

4.1.1. Машины рам и рам*

Рассмотрим две машины:

1. Машины с произвольным доступом к памяти равнодоступная адресная машина - РАМ) моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.

2. Модель с хранимой программой - это машина с произвольным доступом к памяти и возможностью модификаций команд (РАМ*).

Рис.2.9 Структура машин РАМ (РАМ*)

Для РАМ программа не записывается в память, поэтому программа не изменяет саму себя. Программа - последовательность помеченных команд. Имеются арифметические команды, команды ввода-вывода, команды косвенной адресации и команды разветвления. Все вычисления производятся в регистре r 0 (сумматор), который, как и любой другой регистр памяти, может хранить произвольное целое число. Каждая команда состоит из двух частей - кода операции и адреса. РАМ-команды являются подмножеством команд языка Ассемблер; это подмножество можно по желанию расширить, но при этом порядок сложности задач не изменится.

Операнд может быть одного из следующих типов:

1. =i означает само целое число i и называется литералом;

2. i - содержимое регистра i (i должно быть неотрицательным);

3. *i означает косвенную адресацию, то есть значением операнда служит содержимое регистра j ,где j - целое число, которое находится в регистре I ;если j<0, машина останавливается.

Можно определить значение программы Р с помощью двух объектов: отображения c из множества неотрицательных целых чисел в множество целых чисел и “счетчика команд”, который определяет очередную выполняемую команду. Функция c есть отображение памяти, а именно с(i)- целое число, содержащееся в регистре с номером I (содержимое регистра I ).

Вначале с(i)=0 для всех i  0 , счетчик команд установлен на первую команду в Р, а выходная лента пуста. После выполнения k -й команды из Р счетчик автоматически переходит на (k+1) -ю (то есть на очередную) команду, если k -я команда не была командой вида JUMP, HALT, JGTZ и тому подобное.

РАМ*-программа находится в регистрах памяти. Каждая РАМ*-команда занимает два последовательных регистра памяти: первый регистр содержит код операции, второй - адрес. Набор команд для РАМ* совпадает с соответствующим набором для РАМ во всем, кроме косвенной адресации, которая исключена: РАМ* может моделировать косвенную адресацию путем изменения команд в процессе выполнения программы.