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

Возможно, наиболее распространенной ошибкой при выборе алгоритма является упущение характеристик производительности. Более скоростные алгоритмы, как правило, сложнее, чем прямые решения, и разработчики часто предпочитают более медленные алгоритмы, дабы избежать дополнительных сложностей. Однако, как это было для алгоритмов union-find, можно добиться значительных улучшений с помощью даже нескольких строк кода. Пользователи удивительно большого числа компьютерных систем теряют существенное время, ожидая, пока простые квадратичные алгоритмы решат задачу, в то время как доступные N logvV или линейные алгоритмы ненамного сложнее, но могут решить задачу быстрее. Когда мы имеем дело с большими задачами, у нас нет другого выбора, кроме как искать наилучший алгоритм, что и будет показано далее.

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

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

Упражнения

2.1 Перевести программу в главе 1 на другой язык профаммирования и ответить на вопросы упражнения 1.22 для вашей реализации.

2.2 Сколько времени займет посчитать до 1 миллиарда (не учитывая переполнение)? Определить количество времени, необходимое программе

int i, j, к, count = О ;

for (i = 0; i < N; i++)

for (j = 0; j < N; j++)

for (k = 0; к < N; k++)

count++;

для выполнения в вашей среде для = 10, 100 и 1000. Если ваш компилятор имеет свойства по оптимизации, которые должны делать программы более эффективными, проверьте, дают ли они какой-либо результат для этой программы.

2.2 Анализ алгоритмов

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

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

Для сравнения разных алгоритмов, предназначенных для решения одной задачи

Для приблизительной оценки производительности программы в новой среде

Для установки значений параметров алгоритма

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

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

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

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

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

Первый шаг при анализе алгоритма состоит в определении абстрактных операций, на которых основан алгоритм, чтобы отделить анализ от реализации. Так, например, мы отделяем изучение того, сколько раз одна из реализаций алгоритма union-find запускает фрагмент кода i = a[i], от подсчета, сколько наносекунд требуется для выполнения этого фрагмента кода на данном компьютере. Для определения реального времени выполнения программы на заданном типе компьютера требуются оба упомянутых элемента. Первый из них определяется свойствами алгоритма, последний - свойствами компьютера. Такое разделение зачастую позволяет сравнивать алгоритмы таким способом, который не зависит от определенной реализации или от определенного типа компьютера.

Хотя количество используемых абстрактных операций может оказаться очень большим, в принципе, производительность алгоритма обычно зависит от нескольких величин, причем наиболее важные для анализа величины, как правило, определить несложно. Один из способов их определения заключается в использовании механизма профилирования (механизма, доступного во многих реализациях С++, который включает в себя счетчик количества выполнений каждой инструкции) для нахождения наиболее часто исполняемых частей программы по результатам нескольких пробных запусков. Или же, как алгоритмы union-find из раздела 1.3, наша реализация может быть построена лишь на нескольких абстрактных операциях. В любом случае, анализ сводится к определению частоты исполнения нескольких фундаментальных операций. Наш образ действия заключается в том, чтобы отыскать приблизительные оценки этих величин, будучи уверенными, что для важных программ при необходимости можно будет произвести полный анализ. Более того, как будет показано далее, часто можно воспользоваться приближенными аналитическими результатами в сочетании с эмпирическим изучением, чтобы предсказать результаты достаточно точно.