Эффективность алгоритмов

Сентябрь 3, 2022

Главная
Алгебра
Эффективность алгоритмов

Содержание

2. алгоритма может быть зависима от других инструкций или результатов их работы. Алгори́тм — точный набор инструкций,
3. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые
4. Анализ алгоритмов – совокупность действий, в результате которых оцениваются какие-либо параметры алгоритма (эффективность, сложность, правильность, трудоемкость,…).
5. Временная эффективность алгоритма обычно выражается как функция размера входных данных n (в ряде алгоритмов для оценки
6. Поскольку конкретные временные характеристики алгоритма зависят от его реализации, использованного компилятора и компьютера, для оценки эффективности
7. Для того чтобы можно было классифицировать и сравнивать между собой порядки роста, введены три условных обозначения
8. Такая оценка функции трудоемкости алгоритма называется сложностью алгоритма и позволяет определить предпочтения в использовании того или
9. Оценка О (О большое). В отличие от оценки Θ, оценка О требует только, что бы функция
10. Оценка Ω (Омега). В отличие от оценки О, оценка Ω является оценкой снизу – т.е. определяет
11. Рассмотрим важность эффективности алгоритмов на графике, изображенном ниже: коричневая линия: сортировка пузырьком; синяя линия: шейкер-сортировка; розовая
12. Трудоёмкость алгоритма. Под трудоёмкостью алгоритма для данного конкретного входа – Fa(N), будем понимать количество «элементарных» операций
13. Проанализируем алгоритм сортировки методом вставки списка из n элементов. В лучшем случае потребуется n-1 сравнений, для
14. При использовании алгоритма двоичного поиска из n элементов потребуется проанализировать не более log2 и элементов. Это
16. Скачать презентацию

Слайд 2

алгоритма может быть зависима от других инструкций или результатов их работы.
Алгори́тм —

точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок».
Это связано с тем, что работа каких-то инструкций

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

(в ряде алгоритмов для оценки размера входных данных может использоваться несколько параметров одновременно — например, в алгоритмах для работы с графами такими параметрами являются количество вершин и количество ребер графа). В большинстве случаев выбор такого параметра не составляет труда. Например, для задач сортировки, поиска, нахождения наименьшего элемента и многих других алгоритмов обработки списков таким параметром является размер списка. При вычислении значения многочлена степени n р(х}=аnхn +L +а0 таким параметром может быть степень многочлена или количество его коэффициентов, которое на единицу больше степени многочлена. Подобные небольшие отличия не влияют на результаты анализа эффективности алгоритма.

Слайд 6

Поскольку конкретные временные характеристики алгоритма зависят от его реализации, использованного компилятора

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

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

Слайд 7

Для того чтобы можно было классифицировать и сравнивать между собой порядки

роста, введены три условных обозначения

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

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

Слайд 8

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

предпочтения в использовании того или иного алгоритма для больших значений размерности исходных данных. В асимптотическом анализе приняты следующие обозначения:
Оценка Θ (тетта). Пусть f(n) и g(n) – положительные функции положительного аргумента, n ≥ 1 (количество объектов на входе и количество операций – положительные числа), тогда:
f(n) = Θ (g(n)),
если существуют положительные с1, с2, n0, такие, что:
с1 * g(n) ≤ f(n) ≤ c2 * g(n), при n > n0

Слайд 9

Оценка О (О большое). В отличие от оценки Θ, оценка О

требует только, что бы функция f(n) не превышала g(n) начиная с n > n0, с точностью до постоянного множителя:

∃ c > 0, n0 > 0 :
0 ≤ f(n) ≤ c * g(n), ∀n > n0

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

Слайд 10

Оценка Ω (Омега). В отличие от оценки О, оценка Ω является

оценкой снизу – т.е. определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя:

∃ c > 0, n0 >0 :
0 ≤ c * g(n) ≤ f(n)

Слайд 11

Рассмотрим важность эффективности алгоритмов на графике, изображенном ниже:
коричневая линия: сортировка пузырьком;
синяя

линия: шейкер-сортировка;
розовая линия: сортировка
выбором;
желтая линия: сортировка
вставками;
голубая линия: сортировка
вставками со сторожевым
элементом;
фиолетовая линия:
сортировка Шелла.

Слайд 12

Трудоёмкость алгоритма. Под трудоёмкостью алгоритма для данного конкретного входа – Fa(N),

будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.
Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной системы, требуемых алгоритмом для решения конкретных проблем. Очевидно, что для различных областей применения веса ресурсов будут различны, что приводит к следующей комплексной оценке алгоритма:
ψΑ=c1 * Fa(N) + c2 * Μ + c3 * Sd + c4 * Sr,
где ci – веса ресурсов, M – количество машинных инструкций, Sr – память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов), Sd – память для хранения промежуточных результатов.

Слайд 13

Проанализируем алгоритм сортировки методом вставки списка из n элементов. В лучшем

случае потребуется n-1 сравнений, для выполнения задачи, а в худшем n(n-1)/2 сравнений. С помощью тестов можно построить график, который будет характеризовать данный алгоритм.
Из графика видно, что при увеличении длины списка на одно и то же количество элементов время, необходимое для сортировки списка, все больше и больше возрастает. Таким образом, с увеличением длины списка эффективность данного алгоритма уменьшается.

Слайд 14

При использовании алгоритма двоичного поиска из n элементов потребуется проанализировать не

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