Здраствуйте. Все письма, которые вы присылали, я прочёл.
Если у кого-то есть желание написать об алгоритме или задаче, обращайтесь.
В этом выпуске статья, которую прислал Александр
Бакулин.
Анализ алгоритмов
Кому-то заголовок может показаться скучным. И вполне возможно, что
действительно будет немножко скучно, но, уверяю вас, знания, которые
вы сегодня получите, пригодятся при использовании и (главное) выборе
алгоритмов для своих задач.
Итак, что же можно в алгоритмах исследовать и зачем? Если начать со
второго вопроса, можно смело сказать, что анализировать алгоритмы мы
будем не из мазохизма, а с вполне определенной целью: мы хотим выбрать
для нашей практической задачи такой алгоритм, чтобы сочетание скорости
работы, надежности и универсальности было удовлетворительным.
Среди ключевых характеристик алгоритма можно выделить следующие:
1. Скорость работы алгоритма (сколько бессонных ночей мы проведем у
монитора в ожидании окончания работы программы?);
2. Универсальность алгоритма (сможем ли мы применить алгоритм ко всем
возможным входным данным, или есть какие-то ограничения?);
3. Точность алгоритма (можно ли верить тому, что мы увидим на экране?).
Пройдемся по всем трем пунктам отдельно.
Скорость работы алгоритма. Думаю, никто не будет спорить,
что скорость – это как раз то, что мы ожидаем от нашей программы больше
всего. Но, к сожалению, не всегда, нажав клавишу или щелкнув мышкой,
мы мгновенно видим результат – приходится иногда и подождать, и немало.
Умные американские дядьки, которые в программировании понимали немного,
стали проблему эту решать прямо – начали выпускать все более быстрые
процессоры и все более емкую память. Разумеется, старые программы после
такого вмешательства стали работать быстрее, но, как говорится, аппетит
во время еды приходит, - и появились новые задачи, способные легко и
непринужденно подвесить самый наикрутейший Пентиум на пару суток.
Мораль сей непонятной преамбулы такова: любая программа на разных компьютерах
ведет себя по-разному. На продолжительность работы при одинаковых входных
данных влияет буквально все: скорость и количество процессоров, характеристики
и объем памяти, частота системной шины… Перечислять можно долго. Про
операционную систему и активные процессы уж совсем молчу. Иногда даже
танец с бубном вокруг системного блока может существенно сократить время
работы программы.
И что прикажете делать? Как нам в таких изменчивых условиях оценивать
производительность алгоритма? Вот умные люди думали-думали, и придумали.
И назвали они то, что придумали, О-нотацией.
Как правило, для каждого алгоритма можно выделить так называемый главный
параметр (primary parameter), который представляет собой, так сказать,
меру входных данных. Это может быть степень полинома, размер входного
файла, число символов в строке и т.д. Чаще всего этот параметр пропорционален
величине обрабатываемого набора данных. Чтобы не путаться, решили называть
этот параметр N.
Скорость алгоритма будем оценивать не абсолютной величиной, а функцией
от N, значению которой пропорционально время работы алгоритма. Например,
у нас есть матрица NxN. И наш алгоритм должен прибавить к каждому элементу
матрицы единицу. В таком случае нам придется написать два вложенных
цикла, которые и будут осуществлять эти действия. Здесь время работы
программы пропорционально N*N. Причем это утверждение будет верным,
что бы мы ни делали с каждым элементом матрицы – прибавляли единицу
или вычисляли пятую степень логарифма – все равно время работы будет
пропорционально N2. Обращаю ваше внимание: не путайте понятия «время
работы равно …» и «время работы пропорционально …».
Так вот, если время работы некоторого алгоритма пропорционально некоторой
функции f(N), то говорят, что этот алгоритм имеет скорость O(f(N)) или
просто – алгоритм является O(f(N)) (в нашем примере – O(N2)).
Универсальность алгоритма. Вот эта штука, хотя и не
видна невооруженным глазом, доставляет гораздо больше проблем, чем скорость
работы. Действительно, можно ли сказать, что алгоритм на определенном
наборе данных не сойдет с ума и не станет выдавать полную чушь? Как
правило, такой набор данных существует и вводится в программу один-единственный
раз – при сдаче ее заказчику. Закон подлости, однако.
Примеров можно приводить много, но среди всех подобных ограничений алгоритмов
можно выделить две категории:
1. Ограничения, накладываемые самим алгоритмом. Ну тут понятно – просто
на некоторых наборах данных алгоритм даже теоретически не может выдать
правильный ответ. Скажем, метод Зейделя решения СЛАУ требует, чтобы
матрица системы была особого вида, иначе решения мы не получим.
2. Технические ограничения. Здесь простор для фантазии богатейший: нельзя,
скажем, в DOS сделать массив длиной больше 64 Кб. Нельзя рекурсию делать
очень глубокой – рано или поздно стек кончится. И вообще, много чего
нам компьютеры не позволяют.
Каким образом проверять, подходит ли вам алгоритм – решать вам. Существует
множество методов тестирования, отладки, анализа и т.п. – ищите, пользуйтесь.
Разумеется, это все относится только к пункту 2, потому что ограничения,
накладываемые самим алгоритмом, нужно учитывать еще до написания программы.
Точность алгоритма. Здесь трудно сказать что-то такое
всеобъемлющее, что бы подходило ко всем существующим алгоритмам, тем
более что для некоторых из них понятие точности вообще не применимо.
Точность чаще всего имеет значение при разработке алгоритмов, использующих
численные методы. В этом случае точность показывает, на сколько полученное
решение отстоит от точного (аналитического).
Для измерения точности используется о-нотация (обратите внимание, что
здесь буква «о» маленькая, да и смысл несколько другой). В качестве
определяющего параметра здесь обычно выбирается шаг разбиения, присутствующий
почти во всех численных методах, который мы обозначим h. Тогда, если
величина погрешности пропорциональна некоторой функции g(h), говорят,
что алгоритм (или метод) имеет точность порядка o(f(h)).
Как правило, приемлемой считается точность о(h2), а точность о(h4) считается
очень хорошим результатом.
Как, наверное, догадались некоторые особо сообразительные, точность
алгоритма оказывает прямое влияние на его скорость. Дело в том, что
шаг разбиения h является одним из входных параметров. Обычно время работы
программы зависит от h обратным образом (чем меньше шаг разбиения, тем
больше итераций придется сделать). Тогда, при переходе с алгоритма точности
о(h2) на алгоритм точности о(h4) для обеспечения заданной точности сгодится
и существенно больший шаг и, как следствие, гораздо меньше времени будет
тратиться на вычисления.
