Презентация на тему Сложность алгоритмов

алгоритмов

существует ли алгоритм решения той илииной задачи.

Если да, то можно ли им воспользоваться на практике, при современном уровне развития вычислительной техники?

Т.е. способен ли компьютер за приемлемое время получить результат?

для размещения данных и программы,
времени процессора по обработке этих

данных.

получение результата в приемлемое время в ограниченном объеме оперативной

памяти.

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

сложность – объем требуемой памяти

Для определения

сложности алгоритма оценивают временную сложность алгоритма

выполненных им элементарных операций (не в секундах!)

Позволяет оценивать именно качество алгоритма, а не свойства исполнителя (быстродействие компьютера)

Размер задачи (n) - объем входных данных, необходимых для ее решения.

которая каждому размеру задачи n ставит в соответствие максимальное

количество элементарных операций выполненных в ходе выполнения алгоритма

вычисления значения многочлена степени n в заданной точке x
Pn(x)

= anxn + an-1xn-1 + ... + aixi + ... + a1x1 + a0

Алгоритм 1:
для каждого слагаемого, кроме a0 возвести x в заданную степень последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить.
Вычисление i-го слагаемого(i=1..n) требует i умножений.
Значит, всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений.
Кроме того, требуется n+1 сложение.
Всего n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 операций.

в виде
Pn(x) = a0 + x(a1 + x(a2 +

... ( ai + .. x(an-1 + anx))).

Будем вычислять выражение изнутри.
Самая внутренняя скобка требует 1 умножение и 1 сложение.
Ее значение используется для следующей скобки...
И так, 1 умножение и 1 сложение на каждую скобку, которых.. n-1 штука.
И еще после вычисления самой внешней скобки умножить на x и прибавить a0.
Всего n умножений + n сложений = 2n операций.

используется их асимптотическая сложность O() , т. е. скорость

роста количества операций при больших значениях n.

+ 1
возрастает приблизительно как n2

Отбрасываем:
- сравнительно медленно растущие слагаемые (3n/2+1)
- константные множители 1/2

Получаем асимптотическую оценку сложности для алгоритма 1: O(n2) (О – нотация)

Читается как "О большое от эн квадрат".

берется наиболее быстро растущая часть T(n).

Например, если

в программе одна функция, например, умножение, выполняется O(n) раз, а сложение - O(n2) раз, то общая сложность программы - O(n2)

с одинаковым O() могут иметь различную эффективность

Например,

один алгоритм делает 2n+1 операций, а другой - 2500n + 1000. Оба они имеют оценку O(n), так как их время выполнения растет линейно.

быстрее алгоритма O(n) при малых n.

Например, реальное

количество операций первого алгоритма может быть n2 + 10n + 6,
а второго - 1000000*n + 5. (больше умножений)

Впрочем, второй алгоритм рано или поздно обгонит первый... n2 растет куда быстрее 1000000*n.

пусть у нас есть O(log2n),
но log2n=log3n/log32, а log32,
как и

любую константу, О() не учитывает.
Таким образом, O(log2n) = O( log3n).
К любому основанию мы можем перейти аналогично, а значит и писать его не имеет смысла.

алгоритмы, схожие по временной сложности, называется классом сложности

Наиболее часто встречающиеся классы сложности :

алгоритмы, использующие часть входных данных и игнорирующие все остальные

данные. Такие алгоритмы выполняется за один проход вне зависимости от значения n

Пример
Дан массив A длины n. Вычислить сумму первых трех элементов массива

Решение этой задачи содержит всего один оператор:
S := A[1] + A[2] + A[3], Т(n) = 3

алгоритмов поиска

массив, в котором элементы упорядочены по возрастанию.

Найти в нем

заданное значение x или сообщить,
что его нет.

Применяется метод двоичного поиска (дихотомии): сначала ширина интервала поиска — все n элементовмассива. На каждом шаге этот интервал делится на 2, процесс завершается, когда левая и правая границы интервала совпадут.

Для алгоритмов класса O(n) для каждого входного элемента выполняется

только одно действие.

На самом деле, может быть, конечно, не одно, а два, три, и т.д., но главное не больше С*N, где С — константа.

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

в котором элементы расположены в произвольном порядке. Найти в

нем заданное значение x или сообщить, что его нет.

Решение этой задачи сводится к последователь-
ному просмотру всех элементов массива

равно T(n) = n, поэтому он имеет линейную сложность.

имеет

Пример:
алгоритмы быстрой сортировки, сортировки слиянием и

"кучной" сортировки

Для алгоритмов класса O(n2) каждый входной элемент обрабатывается (или

проходится) С*n2 раз. Это означает (для наглядности, только как одну из возможностей) наличие вложенных (двойных) циклов.

Пример:
в основном, все простейшие алгоритмы сортировки

массиву элементы попарно сравниваются между собой: 1й со 2м,

затем 2й с 3м, следом 3й с 4м и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами.

2. Постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной

3. При 2м проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

4. На 3м проходе уже не надо сравнивать предпоследний и 3й элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.

5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен.

m – это количество элементов массива.
8.Количество сравнений в каждом

проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
9. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

просмотреть его n-1 раз, каждый раз уменьшая диапазон просмотра

на один элемент.
Количество сравнений n-1+n-2+n-3+…+1 = n(n-1)/2
Количество присваиваний 3(n-1+n-2+n-3+…+1) = 3n(n-1)/2

T(n) = n(n-1)/2 + 3n(n-1)/2

(arr).

2. Поместить его на последнее место (j).

3. Элемент, находившийся

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

4. Уменьшить просматриваемую область массива на единицу (j – 1).

5. Снова найти максимальный элемент в оставшейся области.

6. Поместить его в конец просматриваемой области массива.
и т.д.

будет равно n-1, при этом число сравнений будет одним

и тем же.
В общем случае
Количество сравнений n-1+n-2+n-3+…+1 = n(n-1)/2
Количество присваиваний 3(n-1)
T(n) = n(n-1)/2 + 3(n-1)

В алгоритмах класса O(n3) каждый элемент обрабатывается С*n3 раз

(цикл-в-цикле-в-цикле)

Пример:
умножение матриц размера n*n

Все вышеперечисленные классы являются подклассами общего класса: O(nx), где

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

Также этот класс алгоритмов называют Р-класс.

работающие с полиномиальной скоростью, считаются быстрыми.

Поэтому

очень много исследований посвящено вопросам типа "возможен ли для данной задачи полиномиальный алгоритм"?

У экспоненциальных алгоритмов сложность увеличивается быстрее

любого полинома.

Большинство экспоненциальных алгоритмов – это варианты полного перебора.

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

сочетаний, перестановок

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

техники

для определения сложности алгоритма оценивают не пространственную, а временную

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

3. Что характеризует асимптотическая оценка сложности алгоритма?

4. В каких случаях алгоритм, имеющий асимптотическую сложность O(n2), может работать быстрее, чем алгоритм с асимптотической сложностью O(n)?

5. Какие классы алгоритмов считаются „медленными“?