1. Основы анализа алгоритмов. [4 ч.1, гл.17, гл.34.]

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

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

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

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

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

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

При анализе алгоритмов существуют две фундаментальные проблемы

1. Какими свойствами обладает данный алгоритм

2. Какие свойства должен иметь любой алгоритм, решающий данную задачу.

Первая задача напрямую связана с реализацией (предполагается, что алгоритм задан) и по существу связан с оценкой качества предлагаемого решения (верхние оценки)

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

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