Структуры данных и эффективность алгоритмов. 4
 Скачать 2.32 Mb.
|
1.1. Основы анализа алгоритмов. [4 ч.1, гл.17, гл.34.]То, что анализ алгоритмов полезен и потому важен в практическом программировании – это достаточно понятно. Но при этом возникает много вопросов – что, как и почему имеет смысл анализировать, до какой степени глубины анализ еще обоснован, а когда вложения в анализ являются обременительными и не окупают сделанных затрат. Грамотный программист достаточно быстро может выявить в своей программе места повторных вычислений, а значит потери времени, так же как и места перерасхода памяти... В процессе разработки программы он вносит исправления в программу, по возможности устраняя перерасход времени и памяти, к тому же всегда имеется возможность прогона программы на серии практических примеров. Возникает вопрос о необходимости анализа сложностных оценок в практическом программировании. С одной стороны, дело обстоит действительно так, и нет оснований это оспаривать, но с другой стороны, все это только подчеркивает, что всеобъемлющий анализ алгоритмов – является очень сложной проблемой. А потому даже для ориентировочной оценки качества алгоритма необходимо понимать, как это можно сделать, если конечно мы хотим иметь достаточно весомые основания объективности и реалистичности этой оценки... Обычно время работы программы зависит от входных данных, а потому экспериментальное тестирование программы с целью оценить время ее работы тоже требует специального анализа для обоснованного подбора серии тестов.10 Хорошо известно, что обычно и плохой программе можно подобрать вход, на котором она хорошо работает, и хорошей программе можно подобрать вход, на котором она плохо работает, по крайней мере - не лучше других. К тому же экспериментальное тестирование возможно и покажется нам достаточным, если оно покажет приемлемые характеристики программы, а если нет... Сказанное ни в коей мере не принижает роль экспериментального тестирования в оценке характеристик программы, сказанное только акцентирует внимание на том, что обоснование экспериментальных оценок – не менее сложная проблема, чем в случае аналитического подхода к оценке характеристик программы, если конечно мы хотим иметь достаточно весомые основания объективности и реалистичности этой оценки. Попытки оптимизации программы зачастую приводят к неоднозначным результатам. Некоторые из таких ситуаций встречаются в вышерассмотренных примерах. Варианты устранения одних как бы недостатков приводят к программам либо с другими недостатками, либо к существенно другим программам. А вопросы остаются - был ли выигрыш, а если был – насколько он существенный. Отметим еще одно важное различие между экспериментальными и аналитическими оценками. Чтобы заниматься экспериментальными оценками - программу надо уже иметь, а аналитические могут помочь нам в решении вопроса – имеются ли достаточные основания заниматься реализацией тех или иных или даже всех других вариантов алгоритма решения задачи. Важная проблема, с которой мы сталкиваемся при эмпирическом анализе, — это определение природы входных данных и других факторов, оказывающих прямое влияние на производимые эксперименты. Обычно существуют три основных возможности: реальные данные, случайные данные и ошибочные данные. Реальные данные позволяют точно измерить параметры используемой программы; случайные данные гарантируют, что наши эксперименты тестируют алгоритм, а не данные; ошибочные данные гарантируют, что наши программы могут воспринимать любой направленный им ввод. При анализе алгоритмов существуют две фундаментальные проблемы
Первая задача напрямую связана с реализацией (предполагается, что алгоритм задан) и по существу связан с оценкой качества предлагаемого решения (верхние оценки) Вторая задача связана с изучением внутренних связей задачи, учет которых необходим при любой реализации (проблема нижних оценок) Далее мы сосредоточим внимание в основном на вопросах аналитической оценки времени работы алгоритмов. Рассматриваемые понятия аналогично вводятся и для оценки памяти, расходуемой программой, хотя конечно в вопросах оценки памяти имеются и свои особенности. К тому же и с теоретической и с практической точки зрения большой интерес представляет вопрос о взаимосвязи ресурсов времени и памяти. Известны ситуации, когда удается уменьшить расход времени за счет увеличения расхода памяти, известны и примеры уменьшения расхода памяти за счет увеличения расхода времени. Известны даже некоторые приемы, позволяющие получать такие эффекты. Проблематика анализа алгоритмов многообразна и обширна... |