Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ну это я так для краткости обозвал. Ну хорошо, пусть будет... 04.03.05 15:06 Число просмотров: 2856
Автор: NickP Статус: Незарегистрированный пользователь
|
> > Потом смотрим основную теорему №5. Там сказано, что > число > > шагов алгоритма не может превышать m, число строк > таблицы. > > Не число шагов алгоритма, а число вариантов анализа > таблицы.
Ну это я так для краткости обозвал. Ну хорошо, пусть будет число вариантов анализа таблицы.
Но сложность каждого варианта нигде не раскрыта!
> > Но во-первых m лежит в диапазон 0 <= m <= 2^n, > где n > > - число переменных. > > Решаем задачу ВЫП, её размеры - это не n.
Ладно, сознаюсь. Я не знаю как измеряются размеры задачи ВЫП, расскажите если не сложно. Но мне всетаки казалось что количество переменных - определяющий фактор. Т.к. верхняя граница скорости выполнения как раз и задается полным перебором 2^n вариантов.
> На каждом шаге анализа таблицы просматриваем один столбец. > Следовательно на одном шаге просматривается не более m > ячеек таблицы. Для каждого варианта столбцы просматриваются > последовательно, двигаясь в левую сторону, следовательно > при каждом варианте анализа просматривается не больше n > столбцов и не больше m*n ячеек, то есть таблица > просматривается при каждом варианте не более одного раза. > До получения ответа на вопрос о выполнимости таблицы > просматриваем её не более m раз.
Ладно. Допустим на каждом шаге мы просматриваем один столбец.
Тогда получается, что для каждого "вывода" нужно просмотреть всю таблицу.
Вывод - это выход на вариант 1-3. НО! выход на вариант 1 - это еще не конец "анализа"
таблицы, после получения варианта 1, мы должны снова проанализировать часть таблицы,
а потом снова и снова. Нигде не показана сложность вытекающая из этой рекурсии.
А если внимательно присмотреться к приводимым примером легко можно заметить, что
чаще всего происходит ПОЛНЫЙ перебор некоторого подмножества переменных, и только
часть переменных отсеивается в дальнейшем.
|
|
|