Оценка сложности алгоритма
Тема 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] Ak <L<Ak+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 – размерность просматриваемого массива.
Сколько раз рассматриваем интервалы при делении отрезка пополам? р= Log2 N
Следовательно, учитывая среднее выполнение операций, имеем С *Log2 N = О(Log2 N)
Рекурсия
Иногда оказывается более удобным свести задачу к другой, более простой задаче, а иногда - свести задачу к ней же самой, упростив исходные данные.
Пусть известно, как решать задачудля простейших исходных данных и как сводить ее к боле простым исходным данным во всех остальных случаях. Если несколько последовательных этапов упрощения наверняка приводят задачу к известному простому случаю, то можно считать, что получено решение задачи.
Способ сведения задачи к ней же самой, но с измененными исходными данными, называется рекурсией. Алгоритм решения задачи, который содержит обращения к себе, называется рекурсивным алгоритмом.
Основой для разработки рекурсивных алгоритмов могут служить рекуррентные соотношения (формулы) устанавливающие зависимости между результатами каких-либо действий (операций) на n - ом шаге от результатов аналогичных действий (операций), полученных на предыдущем n-1 - м шаге.
При составлении рекурсивной программы встает, по крайней мере, четыре проблемы:
1. завершение программы;
2. верность алгоритма;
3. быстродействие;
4. глубина рекурсии.
Обсудим пути их решения.
1. Подобно операторам цикла рекурсия может привести к не заканчивающимся вычислениям, поэтому рекурсивное обращение к процедуре должно управляться некоторым условием. Необходимо убедится, что с каждым вызовом рекурсивной процедуры параметр, входящий в условие окончания рекурсии, изменяется по определенному закону и что множество, составленное из значений этого параметра в соответствии с данным законом, конечно, т.е. рано или поздно условие окончания выполнится.
2. Чтобы проверить верность программы, содержащей рекурсивный вызов, нужно составить цепочку вызовов и проследить ее от конца к началу или придумать соответствующий инвариант.
3. Третья проблема - быстродействие. Другими словами, следует оценить, целесообразно ли использовать рекурсию в данном случае или лучше воспользоваться эквивалентной не рекурсивной программой. Рекурсивные программы короче, но менее быстродействены.
4. Наконец четвертая проблема. Важно убедиться, что максимальная глубина рекурсии не только конечна, но и достаточно мала, так как каждая рекурсивная активизация процедуры требует памяти для размещения переменных. Кроме того, нужно еще сохранять текущее состояние вычислений, чтобы можно было вернуться в него по окончании новой рекурсивной активизации процедуры. Необходимо определить, не превысит ли используемая рекурсивной программой память возможностей ЭВМ.
Примеры задач: факториал, Ханойские башни
