Понятие сложности алгоритма реферат

Обновлено: 05.07.2024

Собрала для вас похожие темы рефератов, посмотрите, почитайте:

Введение

Алгоритм — точная инструкция исполнителю выполнить определенную последовательность действий для достижения цели в ограниченном количестве шагов.

Алгоритм может быть сконструирован таким образом, что он может быть выполнен человеком или автоматическим устройством. Создание алгоритма, даже самого простого, — это творческий процесс. Она доступна только живым существам, и долгое время считалось, что она только человеческая. Латинский перевод его математического трактата был подготовлен в 19 в. Европейцы узнали о десятичной системе счисления и правилах арифметики для многозначных чисел. Именно эти правила тогда назывались алгоритмами.

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

Такие качества:

Дискреция (разрыв, разделение) — алгоритм должен представлять процесс решения задачи в виде последовательности простых (или заранее определенных) шагов. Любое действие, предусмотренное алгоритмом, выполняется только после завершения предыдущего.
Определение — каждое правило алгоритма должно быть четким и однозначным и не оставлять места для произвола. Благодаря этой характеристике, выполнение алгоритма является механическим и не требует дополнительных инструкций или информации о решаемой задаче.
Эффективность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.
Массовый — алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим к классу задач, отличающихся только исходными данными. В этом случае исходные данные могут быть выбраны из диапазона, называемого областью действия алгоритма.

Во-первых, неправильно связывать алгоритм с решением проблемы. Алгоритм может вообще не решить проблему.

Типы алгоритмов

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

Линейный алгоритм — набор команд (инструкций), которые выполняются одна за другой во времени.

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

Циклический алгоритм — алгоритм, обеспечивающий многократное повторение одного и того же действия (одних и тех же операций) для новых исходных данных. На циклических алгоритмах сокращено большинство методов вычислений, поиск вариантов.

Цикл программы — это последовательность инструкций (серия, тело цикла), которую можно выполнять много раз (для новых исходных данных) до тех пор, пока не будет выполнено определенное условие.

Вспомогательный алгоритм (алгоритм slave) — алгоритм, который был ранее разработан и полностью использован при алгоритмизации конкретной задачи. В некоторых случаях, когда существуют одинаковые последовательности инструкций (команд) для разных данных, чтобы сократить набор данных, также назначается вспомогательный алгоритм.

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

Структурная (блочная, графическая) схема алгоритма — графическое представление алгоритма в виде схемы, соединенной стрелками (переходными линиями) блоков — графические символы, каждый из которых соответствует одному шагу алгоритма. Внутри блока находится описание соответствующего действия.

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

Требования к алгоритму

В языках программирования выделение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Basic описаны не все переменные, обычно описываются только массивы. Но все же при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и выделяет память для соответствующих переменных.

Третье правило — усмотрение. Алгоритм состоит из отдельных шагов (действий, операций, команд). Множество шагов, из которых алгоритм естественно составлен.

Четвертое правило — тюремное заключение. После каждого шага вы должны указать, за каким шагом следует следующий, или дать команду останова. Пятое правило — конвергенция (эффективность). Алгоритм должен перестать работать после окончательного количества шагов. В этом случае необходимо указать, что следует считать результатом работы алгоритма.

Алгоритм — неопределенный термин в теории алгоритмов. Алгоритм задает конкретный набор выходных данных в соответствии с каждым конкретным набором входных данных, т.е. вычисляет (реализует) функцию.

Заключение

Список литературы

Образовательный сайт для студентов и школьников

Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Работа состоит из 1 файл

Доклад. ЧМ. Сложность алгоритмов.docx

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути.

Представив кару города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы. Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.

Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

Средний и наихудший случай

Оценка сложности алгоритма до порядка является верхней границей сложности алгоритмов. Если программа имеет большой порядок сложности, это вовсе не означает, что алгоритм будет выполняться действительно долго. На некоторых наборах данных выполнение алгоритма занимает намного меньше времени, чем можно предположить на основе их сложности. Например, рассмотрим код, который ищет заданный элемент в векторе A.

Борисоглебск 2009 г.

Содержание
Введение……………………………………………………………………..- 3 -
Анализ алгоритма
1. Основные требования калгоритмам………………………………………………………………-6-
2. Основы оценок сложности алгоритмов………………………. - 12 -
3. Оценка программ…………………………………………………………….….-17-
4. О-Сложность алгоритмов…………………………………………- 20 -
5. Классы сложности…………………………………………………- 27 -
Заключение………………………………………………………………. - 28 -
Список литературы……………………………………………………….- 29 -

Понятие “алгоритм” давно является привычным не только для математиков. Оно является концептуальной основойразнообразных процессов обработки информации. Возможность автоматизации таких процессов обеспечивается наличием соответствующих алгоритмов. С алгоритмами первое знакомство происходит в начальной школе при изучении арифметических действий с натуральными числами. В упрощенном понимании “алгоритм” – это то, что можно запрограммировать на ЭВМ.

Слово алгоритм содержит в своем составе преобразованноегеографическое название Хорезм. Термин “алгоритм” обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми ( Магомет, сын Моисея, из Хорезма ). Он жил приблизительно с 783 по 850 гг., и в 1983 году отмечалось 1200 летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметическоготрактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово “алгоритм” – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

Вплоть до 30-х годов нашего столетия понятиеалгоритма оставалось интуитивно понятным, имевшем скорее методологическое, а не математическое значение. Так, к началу ХХ в. много ярких примеров дала алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождениярациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Дляполучения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале ХХ в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование.

ГОСТ

Основные понятия и применяемая терминология

Сложность алгоритма – это понятие, характеризующее ресурсозатратность алгоритма, как временную (сколько времени нужно центральному процессору для обработки данных), так и связанную с памятью (какой объём памяти ЭВМ требуется для программной реализации алгоритма).

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

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

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

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

Готовые работы на аналогичную тему

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

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

Классификация алгоритмов по их сложности

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

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

По своей вычислительной сложности все алгоритмы подразделяются на несколько классов. Рассмотрим самые основные из них:

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

Анализ сложности алгоритмов

Различия между этими классами алгоритмов становятся явно заметными при решении задач значительно большого размера. В представленной ниже таблице показана скорость нарастания времени исполнения алгоритмов из различных классов в зависимости от объёма входных данных (при их реализации на компьютере с быстродействием 106 операций в секунду).

Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ

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

Рисунок 2. Графики функций. Автор24 — интернет-биржа студенческих работ

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

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

Далее приведём примеры полиномиальных и экспоненциальных алгоритмов:

Именно полиномиальные алгоритмы считаются наиболее эффективными. Примерами полиномиальных алгоритмов являются стандартные алгоритмы целочисленного сложения, умножения, деления, нахождения НОД, перемножения матриц, сортировки массивов, поиска данных и некоторые другие алгоритмы.
К экспоненциальным алгоритмам относятся алгоритмы построения всех подмножеств заданного множества или всех поддеревьев заданного графа. При этом многие экспоненциальные алгоритмы значительно отличаются друг от друга по своей эффективности.

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

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

Существует несколько форм описания алгоритмов:

1. словесное (для решения неформализованных задач)

2. запись с использованием математической либо другой специальной нотации

3. графическое изображение алгоритма

4. запись на метаязыке

5. запись на алгоритмическом языке

Название алгоритма может указывать либо на его назначение, либо на метод решения задачи.

Типы алгоритмов. Сложность алгоритмов.

Существует 2 типа алгоритмов: детерминированные и недетерминированные.

Детерминированные алгоритмыпредполагают прямое решение задачи без использования повторов и выбора вариантов. Такой алгоритм не содержит элементов неопределённости. (Они всегда простые.)

Недетерминированные алгоритмыдопускают повторы, выборы вариантов и использование метода проб и ошибок. Т.е. они содержат некоторый элемент неопределённости. Может использоваться такое понятие, как случайный выбор. Например, поиск оптимального маршрута через лабиринт, поисковый алгоритм нахождения экстремума ф-ции n переменных. (Это сложные алгоритмы.)

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

Некоторые задачи могут быть решены с использованием обоих типов алгоритмов. Например, задача нахождения нужной строки в таблице. Если индекс строки известен, то алгоритм обращения к этой строке является детерминированным. Если индекс строки неизвестен заранее, то для нахождения строки может быть применён алгоритм случайного поиска (недетерминированный) (строка ищется по какому-то признаку и строки перебираются случайным образом). Такой способ эффективен для больших таблиц. Также может использоваться последовательный поиск перебором (II-й недетерминированный алгоритм). При таком методе строка будет найдена за 2n итераций (n-число строк). Последовательный поиск эффективен для малых объёмов.

Сложность алгоритмов

Сложность алгоритма определяет зависимость времени работы алгоритма от объёма обрабатываемых данных.

Основные типы сложности алгоритмов:

1.Постоянная сложность – имеют алгоритмы, рассчитанные на обработку фиксированного объёма данных.

2.Линейная сложность (например, алгоритм обработки массива в памяти). Время работы такого алгоритма может быть оценено так: an+b, где n – количество элементов массива, a – время, необходимое для выполнения операций над отдельным элементом массива, b – время, затрачиваемое на выполнение вспомогательных операций.

3.Квадратичная сложность (например, алгоритм пузырьковойсортировки). (n-1) сравнений для определения I-го элемента,(n-2) – II-го элемента, (n-1)+(n-2)+…+3+2+1= . Для больших n время работы алгоритма ~ .

Сложность алгоритма может оцениваться по уже написанной программе, для чего определяется число внутренних циклов.

Пример оценки сложности по тексту программы (алгоритм сортировки) :

Procedure сортировка;

For k:=1 to n-1 do

For i:=k+1 to n do

If min>A(i) then

В данной прог-е внешний цикл исполняется n-1 раз, а внутренний исполняется в среднем раз.Общее число исполнений внутреннего цикла = . Для больших n количество исполнений ~ . Т.е. алгоритм обладает квадратичной сложностью.

Оценка сложности алгоритма умножения 2-х матриц размерности n*n:

For i:=1 to n do

For j:=1 to n do

For k:=1 to n do

Сложность ~ (т.к. 3 цикла).

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

Читайте также: