Анализ алгоритма.
Анализ – ключ к пониманию алгоритма в степени, достаточной для их эффективного применения при решении практических задач.
Когда нет возможности (а порой необходимости) проводить исчерпывающие эксперименты и глубокий математический анализ каждой программы, алгоритм исследует на основе эмпирического тестирования и приближенного анализа, которые помогают изучить основные характеристики производительности алгоритма, чтобы можно было сравнивать различные алгоритмы и применять их для практических целей.
Анализ играет определенную роль в каждой точке процесса разработки и реализации алгоритмов.
Можно сократить время работы алгоритма на 3-6 порядка за счет выбора правильного алгоритма.
Чем эффективней будут рассматриваемые алгоритмы, тем сложнее будут становиться задачи выбора между ними, поэтому необходимо подробней изучить их свойства.
В погоне за наилучшим алгоритмом необходимо находить как алгоритмы полезные и практические, так и теоретические вопросы, требующие решения.
Эмпирический анализ.
Для эффективного использования алгоритмов, если целью является решение огромной задачи, которую нельзя решить другим способом или если цель заключается в эффективной реализации важной части системы, требуется понимание характеристик производительности алгоритмов.
Один из первых шагов в понимании производительности алгоритма – это эмпирический анализ.
Если есть два алгоритма для решения одной задачи, то в методе нет никакого волшебства: запускаются оба алгоритма и хуже будет тот, который выполняется дольше.
Эта концепция может показаться слишком очевидной, но, тем не менее, это распространенное упущение в сравнительном анализе алгоритмов.
При точных реализаций алгоритмов при типовом вводе получаются результаты, которые являются не только прямым показателем эффективности, но и содержат информацию, необходимую для сравнения алгоритмов и обоснование прилагаемых математических результатов.
Когда эмпирический анализ начинает занимать слишком много времени, то алгоритм анализируется (оценивается) при помощи математического анализа.
Проблемы, возникающие при эмпирическом анализе:
1. Разработка корректной и полной реализации. Для некоторых сложных алгоритмов эта проблема может оказаться сложным препятствием. В соответствии с этим обычно требуются либо с помощью анализа, либо путем экспериментирования с похожими программами установить некоторый признак, который влияет на эффективность реализации алгоритма.
2. Определение природы входных данных и других факторов, оказывающих влияние на производимые эксперименты. Входные данные могут быть трех видов: реальные данные (они позволят точно измерить параметры используемой программы), случайные данные (гарантируют, что наши эксперименты тестируют алгоритм, а не данные), ошибочные данные (гарантируют, что наша программы могут принимать любой направленный. Проблема определения возникает также и при анализе алгоритма.
Способы восприятия:
1. Визуальная
2. Аудиальная
3. Тактильная
4. Вкусовая
5. Обонятельная
· По форме представления
Текстовая
Числовая
Графическая (в виде изображений)
Звуковая (устная или в виде записи)
A. По назначению:
Массовая – содержит тривиальные (простые) сведения, оперирует набором понятий, понятным большей частью социума.
Специальная – т.е. содержит специфический набор понятий, при использовании происходит передача сведений, которые могут быть непонятны основной массе общества, но необходимо и понятно в рамках узкой социальной группы, где используется данная информация.
Секретная – передаваемая узком кругу лиц и по закрытым каналам.
Личная информация – набор сведений, о какой либо личности, определяющий социальное положение и типы социальных взаимодействий внутри популяции.
B. По значению:
Актуальная информация – ценна в данный момент времени.
Достоверная информация – информация, полученная без искажения.
Понятная информация – выражена на языке, на котором она понятна получателю.
Полная информация – достаточная для принятия решения.
Полезная информация – определяется субъектом информации.
Данные – признаки, параметры или записанные наблюдения, сохраняемые в какой либо форме на каком либо носителе. Таким образом, понятие «данные» более узкое, чем информация. Данные превращаются в информацию, как только начинают подвергаться какой либо обработке с определенной целью
1.10.12
При сравнении различных реализаций легко допустить ошибки. Принципиальная опасность при империческом сравнении программ таится в том, что код для одной реализации может быть создан более тщательно, чем для другой.
Ошибки при выборе алгоритма.
Первая или самая распространенная ошибка при выборе алгоритма – упущение характеристик производительности. Более скоростные алгоритмы, как правило сложнее чем прямые решения и разработчики часто предпочитают более медленные алгоритмы что бы избежать дополнительной сложности.
Вторая ошибка – уделять слишком много внимания характеристикам его производительности. Суммарное время, требуемое для реализации отладки улучшенного алгоритма, может быть значительно выше, чем время необходимое для выполнения более медленной программы.
