Объясни словами алгоритм вычисления скалярного произведения двух сжатых (RLE-закодированных) векторов за один проход без их распаковки. Какова асимптотическая сложность по времени?

Скалярное произведение двух RLE-сжатых векторов можно вычислить за один проход, не распаковывая их полностью, используя идею параллельного обхода блоков.

Каждый вектор представлен как последовательность пар (значение, длина), например: [(v1, l1), (v2, l2), ...].

Алгоритм:

1. Инициализируем два указателя на первые блоки каждого вектора.
2. На каждом шаге берем текущие блоки из обоих векторов.
3. Вычисляем минимальную длину блока minLen = min(l1, l2).
4. Добавляем к результату произведение значений блоков, умноженное на minLen: result += v1 * v2 * minLen.
5. Уменьшаем длины блоков на minLen.
6. Если длина блока в одном из векторов стала 0, переходим к следующему блоку этого вектора.
7. Повторяем, пока не пройдем все блоки обоих векторов.

Асимптотическая сложность:

• Время пропорционально суммарному количеству блоков в обоих RLE-представлениях, то есть O(n + m), где n и m — количество блоков в первом и втором векторе соответственно.

Таким образом, мы эффективно вычисляем скалярное произведение без распаковки векторов.