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

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

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

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

Итак, давая оценку быстродействия алгоритма, следует рассмотреть поведение вычислительного процесс в среднем и, отдельно, в экстремальных для него условиях, то есть - в худшем случае.

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

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

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

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

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