Структуры и алгоритмы обработки данных. Ключарев А.А - 7 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

7
– набор допустимых операций, которые применимы к объекту опи-
сываемого типа.
В последующих разделах рассматриваются структуры данных и со-
ответствующие им типы данных. Базы данных детально изучаются в
рамках отдельных дисциплин, и здесь рассматриваться не будут.
При описании элементарных типов и при конструировании состав-
ных типов использовался в основном на язык Паскаль. Этот язык ис-
пользуется и во всех примерах, поскольку он был создан специально
для иллюстрирования структур данных и алгоритмов и традиционно
используется для этих целей. В любом другом процедурном языке про-
граммирования высокого уровня (Си, Фортран и т. д.) без труда можно
найти аналогичные средства.
Анализ сложности и эффективности алгоритмов
и структур данных
В процессе решения прикладных задач выбор подходящего алгорит-
ма вызывает определенные трудности. Алгоритм должен удовлетворять
следующим противоречащим друг другу требованиям:
1) быть простым для понимания, перевода в программный код и отладки;
2) эффективно использовать вычислительные ресурсы и выполнять-
ся по возможности быстро.
Если разрабатываемая программа, реализующая некоторый алгоритм,
должна выполняться только несколько раз, то первое требование наи-
более важно. В этом случае стоимость программы оптимизируется по
стоимости написания (а не выполнения) программы. Если решение за-
дачи требует значительных вычислительных затрат, то стоимость вы-
полнения программы может превысить стоимость написания програм-
мы, особенно если программа выполняется многократно. Поэтому бо-
лее предпочтительным может стать сложный комплексный алгоритм (в
надежде, что результирующая программа будет выполняться существенно
быстрее). Таким образом, прежде чем принимать решение об использо-
вании того или иного алгоритма, необходимо оценить сложность и эф-
фективность этого алгоритма.
Сложность алгоритма – это величина, отражающая порядок вели-
чины требуемого ресурса (времени или дополнительной памяти) в за-
висимости от размерности задачи.
Таким образом, будем различать временную T(n) и пространствен-
ную V(n) сложности алгоритма. При рассмотрении оценок сложности

Страницы