Создать тему  Создать ответ 
Алгоритм Шёнинга
10-11-2012, 10:25    
Сообщение: #11
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Алгоритм Шёнинга
(10-11-2012 01:38)Quasus писал(а):  А «флипанье» значит дорого?
Флипание - это просто замена значение какого-то x[i] на противоположное, поэтому требует О(1) времени.
Можно добавить параметр m - число дизъюнкций, и пытаться получить как можно более хорошую оценку сложности с учётом и n, и m. Тогда для оптимизации поиска невыполняющейся дизъюнкции может понадобиться специальная структура данных, и флипание будет как-то её изменять, возможно, дольше чем за О(1).
Найти все сообщения
Цитировать это сообщение
10-11-2012, 12:06    
Сообщение: #12
Quasus

Гоф-фурьер
Сообщений: 625
Зарегистрирован: 17.06.12

RE: Алгоритм Шёнинга
Никак не уясню правила игры. Какие же операции требуют единицы времени?
Найти все сообщения
Цитировать это сообщение
10-11-2012, 12:14    
Сообщение: #13
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Алгоритм Шёнинга
(10-11-2012 12:06)Quasus писал(а):  Никак не уясню правила игры. Какие же операции требуют единицы времени?
Все операции, скорость выполнения которых не зависит от параметров задачи, выполняются за О(1): поместить число в ячейку памяти, сгенерировать (псевдо)случайное число, сложить-вычесть-умножить конечное два числа и т. д.
Найти все сообщения
Цитировать это сообщение
Создать ответ 


Переход:


Пользователи просматривают эту тему: 1 Гость(ей)