Сложность решений

[thesz]

Декартово произведение множеств A и B в ZDD будет занимать объём |A|+|B| узлов представления.

В ROBDD нам надо добавить множители-логарифмы. Ведь "индекс" элемента из A или B мы записываем в виде последовательности битов. Поэтому размер представления будет log(|A|)|A| + log(|B|)|B|.

Предположим, что мы работаем не с декартовым произведением, а с некоторым его изменением, например, некоторые пары декартова произведения не присутствуют в отношении. Это означает, что нам надо хранить больше, а проверка принадлежности пары (a,b) нашему отношению не тривиальна - надо проверить наличие элемента a в A×B∖delta(A,B), которому будет соответствовать некое подмножество из B, и проверить наличие b в этом подмножестве.

В случае ZDD мы храним конкретные элементы, а не их код. ZDD в случае множества всех элементов {a∈A} это последовательный список, фактически. Поэтому проверка наличия элемента в ZDD для A∖delta(A) будет иметь сложность O(|A|).

А вот в ROBDD эта сложность будет O(log(|A|).

С чем, господа, я вас и поздравляю. ;)

PS
ZDD может быть приближена ROBDD, если мы будем записывать факт наличия a через переменную xa, а не через последовательность битов {bai, i∈0..⌈log2(|A|)⌉}