Модель дерева решений
В вычислительной сложности модель дерева решений — это модель вычислений , в которой алгоритм считается в основном деревом решений , т. е. последовательностью запросов или тестов , которые выполняются адаптивно, поэтому результаты предыдущих тестов могут влиять на тест. выполняется далее.
Как правило, эти тесты имеют небольшое количество результатов (например, вопрос «да-нет») и могут быть выполнены быстро (скажем, с удельной вычислительной стоимостью), поэтому временная сложность алгоритма в наихудшем случае в модели дерева решений соответствует глубина соответствующего дерева решений. Это понятие вычислительной сложности задачи или алгоритма в модели дерева решений называется сложностью дерева решений или сложностью запроса .
Модели деревьев решений играют важную роль в установлении нижних границ теории сложности для определенных классов вычислительных задач и алгоритмов. Было введено несколько вариантов моделей дерева решений в зависимости от вычислительной модели и типа алгоритмов запросов, которые разрешено выполнять.
Например, аргумент дерева решений используется, чтобы показать, что элементы сортировки для сравнения должны принимать сравнения. Для сортировки сравнением запрос представляет собой сравнение двух элементов с двумя результатами (при условии, что элементы не равны): или или . Сравнительная сортировка может быть выражена в этой модели в виде дерева решений, поскольку такие алгоритмы сортировки выполняют только эти типы запросов.
Деревья решений часто используются для понимания алгоритмов сортировки и других подобных задач; это было впервые сделано Фордом и Джонсоном. [1]
Например, многие алгоритмы сортировки являются сортировками сравнения , что означает, что они получают информацию о входной последовательности только посредством локальных сравнений: проверка того , , , или . Предполагая, что все элементы, подлежащие сортировке, различны и сопоставимы, это можно перефразировать как вопрос, на который можно ответить «да» или «нет»: is ?
