Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Оценка алгоритмов в худшем и среднем случаях.
План:
Введение
1. Понятие алгоритма и его определение.
2. Основная часть
2. Оценка алгоритмов.
3. Анализ алгоритмов; лучшее, худшее и среднее время безотказной работы.
III. Заключение


Входить.
Для любого программиста важно знать основы теории алгоритмов, поскольку это наука, изучающая общие свойства алгоритмов и формальные модели их представления. Еще с уроков информатики нас учат составлять блок-схемы, которые помогут нам в будущем писать более сложные задачи, чем в школе. Ни для кого не секрет, что почти всегда есть несколько способов решения той или иной проблемы: одни требуют затрат много времени, другие ресурсов, а третьи чуть ли не помогают найти решение.
Всегда следует искать оптимальный вариант по поставленной задаче, особенно при разработке алгоритмов решения класса задач. Также важно оценить, как ведет себя алгоритм при начальных значениях разных размеров и количеств, какие ресурсы ему нужны и сколько времени требуется для получения конечного результата.
Понятие алгоритма и его определение.
Алгоритм обработки данных — это описание метода решения задач в информатике, который затем может быть реализован в выбранной среде программирования.
Алгоритмический анализ — это область информатики, изучающая оценку алгоритмов.
Сложность алгоритма — это количество элементарных операций, которые учитываются при анализе алгоритма.
Максимальное количество операций, определяемое алгоритмом A, является весом в наихудшем случае, который вводит входные данные D заданного размера.
Трудоемкость — лучший алгоритм работы при небольшом числе операций A во всех элементах D известной размерности n.
Алгоритм средней трудоемкости представляет собой среднее число операций A во всех записях D с известной мерой n.
Функция сложности алгоритма — сложность алгоритма зависит от параметров параметра A на входе D.
Временная сложность алгоритма — это асимптотическая оценка функции сложности алгоритма для наихудшего случая.
Объем памяти — максимальное количество ячеек памяти, задействованных в реализации алгоритма A для ввода D.
Емкостная сложность алгоритма представляет собой асимптотическую оценку функции памяти алгоритма в наихудшем случае.
Сложность ресурсов в худшем, среднем и лучшем случаях алгоритма представляет собой упорядоченную пару классов времени и функции, емкостная сложность определяется асимптотическим символом и соответствует рассматриваемому случаю.
Алгоритмы работы со структурами данных — это алгоритмы, определяющие основные принципы и методологию понимания методов обработки данных.
Алгоритмы сортировки — это алгоритмы, предназначенные для организации массивов и файлов.
Алгоритмы поиска — это алгоритмы, предназначенные для поиска определенных элементов в больших наборах данных.
Алгоритмы графов — это алгоритмы, предназначенные для реализации стратегий вычитания и поиска графов.
Алгоритмы обработки строк — это алгоритмы, содержащие ряд методов обработки последовательности символов.
Геометрические алгоритмы — это алгоритмы решения задач с использованием геометрических объектов.
Оценка алгоритма
Существует несколько способов измерения сложности алгоритма. Программисты обычно ориентируются на скорость работы алгоритма, но не менее важны и другие показатели — объем памяти, требования к дисковому пространству. Использование быстрого алгоритма не даст ожидаемых результатов, если компьютеру требуется больше памяти, чем нужно.
Память или время
Многие алгоритмы предлагают выбор между объемом памяти и скоростью. Проблема может быть решена быстрее, используя больше памяти, или медленнее, занимая меньше. Типичным примером в этом случае является алгоритм поиска кратчайшего пути. Учитывая карту города в виде сетки, вы можете написать алгоритм для нахождения кратчайшего расстояния между любыми двумя точками на сетке. Чтобы не вычислять эти расстояния по мере необходимости, мы можем сохранить результаты в таблице, указав кратчайшее расстояние между всеми точками. Если нам нужно найти кратчайшее расстояние между двумя заданными точками, мы можем просто получить заполненную таблицу расстояний. Результат получается моментально, но требует большого объема памяти. O на карте большого города n может иметь тысячи точек. Тогда описанная выше таблица должна иметь более 10 миллиардов ячеек. Необходимо использовать дополнительные 10 ГБ памяти для повышения производительности алгоритма. Из этой зависимости возникает идея пространственно-временной сложности. При таком подходе алгоритм оценивается с точки зрения скорости выполнения и потребления памяти. Мы ориентируемся на временную сложность, но тем не менее четко определяем объем потребляемой памяти. алгоритм оценивается с точки зрения скорости выполнения и потребления памяти. Мы ориентируемся на временную сложность, но тем не менее четко определяем объем потребляемой памяти. алгоритм оценивается с точки зрения скорости выполнения и потребления памяти. Мы ориентируемся на временную сложность, но тем не менее четко определяем объем потребляемой памяти.
Оценка заказа
При сравнении разных алгоритмов важно знать, что их сложность зависит от количества входных данных. Например, при сортировке по одному методу для обработки тысячи чисел требуется 1 с, а для обработки миллиона чисел — 10 с, а при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно, в таких условиях нельзя однозначно сказать, какой алгоритм лучше. В целом сложность алгоритма можно оценить на порядок. Если с увеличением объема входных данных время выполнения алгоритма увеличивается с той же скоростью, что и функция f(N), то алгоритм имеет сложность O(f(n)). Рассмотрим код, который находит максимальный элемент в каждой строке для матрицы [NxN].
для i:=1 до N сделать
начинать
макс :=А[i,1];
для j:=1 до N сделать
начинать
если A[i,j]>max, то
макс: = А [я, j]
конец
написать(макс);
конец
В этом алгоритме переменная i меняется с 1 на N. При каждом изменении i переменная j также меняется с 1 на N. Для каждой N итерации внешнего цикла внутренний цикл также выполняется N раз. Общее количество итераций внутреннего цикла равно N * N. Это определяет сложность алгоритма как O (N ^ 2). При оценке порядка сложности алгоритма следует использовать только самую быстрорастущую часть. Предположим, что цикл задач описывается выражением N^3 + N. В этом случае его сложность будет O(N^3). Учет быстрорастущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N = 100 разница между N^3 + N = 1000100 и N = 1000000 составляет всего 100, что составляет 0,01%. При вычислении O постоянными множителями в выражениях можно пренебречь. Алгоритм с 3N^3 шагами считается O(N^3). Это делает более очевидным, что отношение O(N) зависит от размера задачи.
Определение трудности
Наиболее сложными частями программы обычно являются циклы и вызывающие процедуры. В предыдущем примере весь алгоритм был реализован с помощью двух циклов. Если одна процедура вызывает другую, то следует более детально оценить сложность процедуры. Если в нем выполняется определенное количество инструкций (например, печать), то это почти не влияет на рейтинг сложности. Если в вызываемой процедуре выполняется O(N) шагов, функция может значительно усложнить алгоритм. Если процедуру вызвать с улицы внутрь, то эффект может быть еще больше. В качестве примера рассмотрим две процедуры: медленную со сложностью O(N^3) и сложностью O(N^2).
процедура Медленная;
var i,j,k: целое число;
начинать
для i:=1 до N сделать
для j:=1 до N сделать
для k:=1 до N сделать
какое-то действие}
конец
процедура Быстрая;
есть
i, j: целое число;
начинать
для i:=1 до N сделать
для j:=1 до N сделать
Медленный;
конец
процедура Оба;
начинать
Быстрый;
конец
Основным показателем сложности алгоритма является время, необходимое для решения задачи, и объем требуемой памяти. Также при анализе сложности для класса задач определяется определенное число, описывающее определенную информацию — размер входных данных. Таким образом, мы можем сделать вывод, что сложность алгоритма зависит от размера входных данных.
Сложность алгоритма может варьироваться в зависимости от одного и того же размера входных данных, но разных входных данных. Есть понятия сложности в худшем, среднем или лучшем. Обычно оценивается сложность наихудшего случая. Временная сложность — это в худшем случае функция размера входных данных, равная максимальному количеству операций, выполняемых за время выполнения алгоритма при решении задачи заданного размера. В худшем случае емкостная сложность является функцией размера входных данных, равного максимальному количеству ячеек памяти, используемых для решения задач такого размера.
Порядок роста алгоритма
Порядок возрастания сложности (или аксиоматическая сложность) описывает приблизительное поведение функции сложности алгоритма с большим размером входных данных. Отсюда следует, что при оценке временной сложности нет необходимости рассматривать элементарные операции, достаточно рассматривать шаги алгоритма.
Шаг алгоритма представляет собой набор последовательных элементарных операций, время выполнения которых не зависит от размера входных данных, то есть ограничено сверху некоторой константой.
Асимптотические типы оценивания
О это худший случай
Рассмотрим сложность f(n)> 0, функцию порядка g(n)> 0, размер входных данных n> 0. Если f(n) = O(g(n)) и существуют постоянные величины c>0, n0>0, то 0n0.
В этом случае функция g(n) является асимптотически определенным значением f(n). Если f(n) — функция сложности алгоритма, то порядок сложности определяется как f(n) — O(g(n)).
Это выражение определяет класс функций, которые не растут экспоненциально от g(n) до постоянного множителя.
TH - балл за среднюю работу
Стоит отметить, что при n > n 0 функция f(n) находится всюду между c 1 *g(n) и c 2 *g(n), где c — постоянный множитель.Например, f (n) = n 2 + n с ; г (п) знак равно п 2 .