Вопрос 2: Значение упорядоченности для двуместных операций над множествами.

Двуместные операции - операции, в которых учавствуют два операнда. К двуместным операциям над множествами относятся:

• Объединение ( $\cup$ )
• Пересечение ( $\cap$ )
• Разность ( $\setminus$ )
• Исключающее ИЛИ, XOR ( $\oplus$ )

Упорядоченное множество может представляться в виде списка или массива. Операции над упорядоченными множествами могут выполняться быстрее, так как имеют меньшую временную сложность. Например, приведенные двуместные операции выполняются на неупорядоченном множестве за $O(n^2)$, а на упорядоченном - за $O(n)$.

Примеры:

/* Пересечение неупорядоченного множества */
vector<int> intersection(const vector<int>& a, const vector<int>& b)
{
    vector<int> c;

    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < b.size(); j++)
            if (a[i] == b[j]) {
                c.push_back(b[j]);
                break;
            }

    return c;
}

/* Пересечение упорядоченного множества  */
vector<int> intersection(const vector<int>& a, const vector<int>& b)
{
    vector<int> c;

    for (int i = 0, j = 0; i < a.size() && j < b.size();)
        if (a[i] > b[j]) {
            j++;
        }
        else if (a[i] < b[j]) {
            i++;
        }
        else {
            c.push_back(b[j]);
            i++; j++;
        }

    return c;
}