Покрытие множества почти последовательными подмножествами: различия между версиями

Теорема 1 [7]. Приведение матрицы A может быть выполнено за время O(Nn) в соответствии с правилом доминирования для столбцов, за время O(Nm) в соответствии с правилом доминирования для строк и за время O(Nmn) в соответствии со всеми тремя описанными выше правилами доминирования, где N – количество единиц в матрице A.

В базах данных, которые использовали Руф и Шобель [ ], матрицы представлены столбцовыми индексами первой и последней единицами в ее блоках последовательных единиц. Для таких матричных представлений было предложено правило быстрой редукции данных [8], которое устраняет «лишние» столбцы и в конкретных реализациях заменяет правило доминирования для столбцов. Новое правило работает быстрее, чем правило доминирования для столбцов (приведение матрицы по новому правилу может быть выполнено за время O(mn)), однако оно является менее мощным: в результате приведения матрицы A с использованием нового правила может получиться матрица с большим числом столбцов, чем в результате приведения A по правилу доминирования для столбцов.