Оценка сложности алгоритма

Тема 1

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

Поиск в упорядоченном и неупорядоченном массивах

Дихотомия

Задача 1.

Дана произвольная целочисленная таблица из n элементов. Определить, есть ли в таблице элемент, равный числу L.

Вопрос: Как осуществить поиск?

Сравнивать L со всеми элементами таблицы, пока не найдем равный ему.

Тесты: 2 ситуации:

Такие элементы есть: k := номер элемента, равного L

Такого элемента нет: k:=0

Задача 2.

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

Допустим, что в таблице нет повторяющихся элементов

Например:

2 3 5 7 8 10 11 15 16

1 2 3 4 5 6 7 8 9

Найти: А[к]=L

к - результат

Тестирование

Какие ситуации возможны на нахождение элемента в таблице ?

Какие значения может принять величина к после исполнения алгоритма?

К= {1,..,9} или к=0

Число есть

На границе в середине

Числа нет

За границами между элементами

интервала ед. длины (соседними)

L<A[1] или L>A[n] A_k <L<A_k+1

k+1 – k = 1

интервал [k, k+1] – ед. длины

Как осуществить поиск в упорядоченном массиве?

1) Методом из 1 задачи (перебор всех подряд идущих элементов)

Это долго, если чисел много

2) Десятками с возвратом или через 1 элемент

3) Более короткий способ: брать число c номером из середины интервала [1, n].

Действия:

1 – Берем число из середины интервала

повторять: 2 – Выбираем интервал: либо левый, либо правый, - тот, в котором

находится искомое число.

До каких пор производить 1 и 2 действия?

Пока не найдем число, т. е. В = А[к] и к – результат либочисла нет, т. к. он между соседними элементами, т. е. длина интервала стала < 1.

Дихотомия

Имеем возрастающий массив. А[1] < A[2] < …….<A[n]

[.^a . . . .^k][ ^k+1. . . .^b]

интервал [1, n] или [a, b]

Берем число посередине с индексом k.

Сравниваем L и A[k]

т. е., проверяем, в какой интервал попало число L

левый L Î [1, k] При каком условии? L <= A[k] Меняем границы интервала [a, b] меняется правая граница b:=k

Правый L Î [k + 1, n] При каком условии? L <= A[k] Меняем границы интервала [a, b] меняется левая граница a:=k+1

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

Поменять индекс к в обоих случаях:

k – середина [а, b]

k=( a + b )/2

Многократные действия: (поиск элемента)

1) Сравнение L и A[к]

2) Смена границ

3) Смена середины

Условия продолжения

До каких пор, пока L< > A[k] иотрезок ед. длины b – a>=1

В каком случае закончит выполняться цикл?

Когда условие нарушается. В каких случаях условие нарушается?

1. L = A[k] либо 2. b – a < 1

тогда к – искомый результат тогда к – получено какое – то

число, но A[k] < > L

После поиска надо сделать проверку полученного индекса k.

Если A[k] – не искомое число, то k:=0.

Но k может быть равно 0 и по другой причине, если число находится за границами интервала.

Замечание:прежде, чем делать поиск, следует проверить наличие числа в интервале [A[1], A[n]]

если нет Þ к:=0

если есть Þ поиск (n, A, L, k)

Величины:

n - кол-во элементов

А – таблица

L – заданное число

К – искомый номер.

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

Проверка L Î [А[1], А[n]]

нет да

к:=0 поиск (n, A, L, k)

ß

проверка найденного числа k

нет да

k:=0 k– искомое

Начальные условия

а = 1 границы первого интервала

b = n

k = ( a + b)/ 2 - середина в первом интервале [а, b]

n = 9 (для тестового примера)

Тестирование

Для таблицы

элемент
№ эл-та

L = 1, 17 – за пределами

2, 16 – на границе первого интервала

L = 3, 15 – левый и правый интервал

8 – посередине первого интервала

12, 4 – между соседями

Оценка сложности алгоритма

Пусть N – размерность просматриваемого массива.

Сколько раз рассматриваем интервалы при делении отрезка пополам? р= Log₂ N

Следовательно, учитывая среднее выполнение операций, имеем С *Log₂ N = О(Log₂ N)

Рекурсия

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

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

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

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

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

1. завершение программы;

2. верность алгоритма;

3. быстродействие;

4. глубина рекурсии.

Обсудим пути их решения.

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

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

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

4. Наконец четвертая проблема. Важно убедиться, что максимальная глубина рекурсии не только конечна, но и достаточно мала, так как каждая рекурсивная активизация процедуры требует памяти для размещения переменных. Кроме того, нужно еще сохранять текущее состояние вычислений, чтобы можно было вернуться в него по окончании новой рекурсивной активизации процедуры. Необходимо определить, не превысит ли используемая рекурсивной программой память возможностей ЭВМ.

Примеры задач: факториал, Ханойские башни