- Теория сложности
- Сложность алгоритмов по памяти
- Сложность алгоритмов по времени
- Операции и параметры по которым производится анализ
- Скорость роста сложности алгоритма
- Классы входных данных
- Анализ в наилучшем, наихудшем и среднем случаях
- -
- Нижняя граница - наименьшее количество операций, необходимое для решения конкретной задачи
- Насколько быстро решается задача на массиве входных данных длины N?
- -
- Разбиение задач на классы по эффективности решающих их алгоритмов
- Использование дерева решений для определения нижней границы сложности
- Алгоритмы сортировки и поиска, на которых основана работа современных систем управления базами данных
- Алгоритмы поиска и выборки
- Алгоритмы сортировки
- Продолжение следует...
Метод турниров можно использовать для решения задач, в которых информация, полученная в результате первого прохода по данным, может облегчить последующие проходы. Поиск наибольшего значения Если воспользоваться им для поиска наибольшего значения, то потребуется построение бинарного дерева, все элементы которого являются листьями. На каждом уровне два элемента объединены в пару, причем наибольший из двух элементов копируется в родительский узел. Процесс повторяется до достижения корневого узла. Полное дерево турнира для фиксированного набора данных: Алгоритм поиска второго по величине элемента списка из N значений, требующий около N сравнений В результате каждого сравнения мы получаем "победителя" и "проигравшего". Проигравших мы забываем, и вверх по дереву двигаются только победители. Всякий элемент, за исключением наибольшего, "проигрывает" в точности в одном сравнении. Поэтому для построения дерева турнира требуется N-1 сравнение. Вт...
Комментарии
Отправить комментарий