Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
| Применения алгоритма поиска в глубину:
Поиск любого пути в графе. Поиск лексикографически первого пути в графе. Проверка, является ли одна вершина дерева предком другой. Поиск наименьшего общего предка. Топологическая сортировка. Поиск компонент связности. Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи. Для реализации алгоритма удобно использовать стек или рекурсию. Оценка сложности алгоритмов (понятие, оценка сложности на примерах алгоритмов упорядочения и поиска) Каждая структура предоставляет алгоритмы, работающие с данными с той или иной сложностью. Сложность понимается как количество элементарных операций, выполняемых вычислительной машиной для решения задачи в зависимости от размера задачи. Размер задачи определяется входными данными. Так, например, для простейшей операции сложения двух натуральных чисел, размером задачи можно считать максимальную длину в битах одного из слагаемых. Для оценки сложности алгоритмов применяется верхняя оценка сложности, выражаемая в –символике. Алгоритм имеет сложность , если время его работы (количество элементарных операций) есть величина (меньшая или равная ), где – некоторая постоянная. Поиск элементов в одномерном массиве имеет сложность – линейную сложность. «Пузырьковая сортировка» массива имеет сложность – квадратичную сложность. O(1) – сложность, представляющая собой константу. Чем меньше сложность, тем быстрее работает алгоритм. Общие функции оценки сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой: N N* Объектно-ориентированное программирование. Инкапсуляция. Наследование. Полиморфизм. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|