#algorithm
#алгоритм
Вопрос:
Задан набор операций (массив значений, массив ячеек памяти), который сохраняет соответствующие значения в соответствующих ячейках памяти и занимает O (1) времени независимо от длины массива. Как вы используете его для вычисления скалярного произведения разреженных векторов со сложностью менее O (n m)? Каждый вектор представлен в виде триплета [val,index,len], где len — количество ненулевых элементов, index — массив индексов ненулевых элементов, а val — массив, состоящий из ненулевых элементов, поэтому размер val = размер индекса =len. Предположим, что индекс массива отсортирован.
Комментарии:
1. Что означает m? Не является ли сложность скалярного произведения двух векторов O (n), поскольку векторы должны быть одинаковой длины?
2. Как представлены эти «разреженные векторы»?
3. Извините за двусмысленность моей постановки задачи. Я отредактировал его для решения ваших конкретных проблем.
4. Как вы можете ожидать, что оно будет выполняться быстрее, чем размер входных данных?
5. Возможно, потому, что у нас есть операция, которая выполняется быстрее, чем размер входных данных