Как написать псевдокод для объединения, пересечения и произведения диаграммы Венна из двух окружностей?

Question

Предположим, у нас есть диаграмма Венна из двух окружностей. Мы должны найти объединение, пересечение и произведение их. Например, у нас есть наборы:

A=[a,b,f,g]
B=[b,e,f,h]

Объединение

AUB=[a,b,e,f,g,h]

Пересечение

A∩B = [f,g]

Продукт

A*B=[ab, ae, af, ah, bb, be, bf, bh, fb, fe, ff, fh, gb, ge, gf, gh]

Мой вопрос, как мы пишем эти операции в псевдокоде? Я не знаю, как это сделать.

Answer 1

A union B:

C := empty set
for each a in A:
    C.add(a)
for each b in B:
    if not C.contains(b) then C.add(b)

Имеет квадратичное c время выполнения, если реализовано с использованием списков / массивов. Он имеет линейное время выполнения, если используется таблица / словарь ha sh.

A пересечение B:

C := empty set
for each a in A:
    if B.contains(a) then C.add(a)

То же, что и объединение.

A x B:

C := empty set
for each a in A:
    for each b in B:
        C.add((a,b))

Это имеет квадратичное c время выполнения, но это неизбежно, так как возвращаемый результат содержит порядка n ^ 2 элементов.