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

Ключевые термины

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

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

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

Худший случай трудоемкости – это наибольшее количество операций, задаваемых алгоритмом А на всех входах D определенной размерности n.

Лучший случай трудоемкости – это наименьшее количество операций в алгоритме А на всех входах D определенной размерности n.

Средний случай трудоемкости – это среднее количество операций в алгоритме А на всех входах D определенной размерности n.

Функция трудоемкости алгоритма – это зависимость трудоемкости алгоритма А от значения параметров на входе D.

Временная сложность алгоритма – это асимптотическая оценка функции трудоемкости алгоритма для худшего случая.

Объем памяти – это максимальное количество ячеек памяти, задействованных в ходе выполнения алгоритма А для входа D.

Емкостная сложность алгоритма – это асимптотическая оценка функции объема памяти алгоритма для худшего случая.

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

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

Алгоритмы сортировки – это алгоритмы, предназначенные для упорядочения массивов и файлов.

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

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

Алгоритмы обработки строк – это алгоритмы, которые включают ряд методов обработки последователей символов.

Геометрические алгоритмы – это алгоритмы решения задач с использованием геометрических объектов.

1. Определение ресурсной эффективности алгоритмов – необходимая составляющая этапа анализа разработанного программного обеспечения.

2. Наиболее значимыми характеристиками ресурсной эффективности алгоритмов являются оценки их временной и емкостной сложности.

3. Временная сложность алгоритма определяется асимптотической оценкой функции трудоемкости алгоритма для худшего случая.

4. В зависимости от вида функции временной сложности алгоритма выделяют пять основных классов сложности алгоритмов.

5. Емкостная сложность алгоритма определяется как асимптотическая оценка функции объема памяти алгоритма для худшего случая.

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

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

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

9. В зависимости от структур обработки данных в процедурном программировании выделяются классы базовых алгоритмов.

Дата добавления: 2014-01-04