Дополнительные ограничения для практических вычислений:

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

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

3. Ограничение объема памяти для вычислений.

Анализ алгоритмов и их вычислительная сложность

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

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

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

Способы анализа алгоритмов:

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

2. Анализ алгоритмов, записанных на языке высокого уровня или псевдокоде, реализующем основные структуры управления (циклы, ветвления и др.).

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

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

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

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

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

Время выполнения алгоритмов в наилучшем случае очень часто оказывается маленьким или просто постоянным, поэтому анализ наилучшего случая проводится редко.

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

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

Пример.

Рассмотрим два алгоритма поиска слова в списке, поиск перебором и бинарный поиск. Задание к лабораторной работе № 2 включало в себя построение графиков и сравнение эффективности алгоритмов. Рассмотрим эту задачу с точки зрения теории.

Предполагается, что целевое слово в списке точно присутствует.

Рассмотрим поиск перебором в списке длиной N.

Начиная с первого слова в списке, пока слово не найдено:

а) Если целевое слово не совпадает с текущим словом, перейти к следующему.

б) Если целевое слово совпадает с текущим, завершить поиск.

Пусть в списке N слов. Какое максимальное количество шагов может потребоваться для того, чтобы найти в списке слово? В наихудшем случае придется перебрать весь список. Это означает, что количество необходимых шагов алгоритма в худшем случае – N. Время работы этого алгоритма приблизительно пропорционально N.