Вычислительная временная сложность разреженной матрицы (2)

Question

У меня есть набор данных (D) of (nxd), где n = количество строк и d = количество измерений, я создаю матрицу подобия (S) (nxn) на сравнивая каждую строку набора данных (D), а затем преобразовывая ее в разреженную матрицу (tx3), где t - число ненулевых элементов матрицы симметричного подобия (S)

Сложность времени создания сходства матрица равна o (n^2d), где d - некоторая постоянная операция. Временная сложность преобразования разреженной матрицы является тета (п^2)

Мой вопрос: При создании матрицы подобия, если я выполнить проверку, что «если значение подобия является„ноль“, то продолжить (продолжение) иначе положить его в разреженную матрицу ». Предполагая это, можно сказать, что стоимость вычисления разреженной матрицы из набора данных (D) равна O (n^2 d).

Например:

Создание схожесть матрицы:

for i in range(0,n): 
    for j in range(0,n): 
     find similarity_value of D[i] and D[j] 
     insert into similarity_matrix: S[i,j]= similarity_value 

The above runs in O(n^2 d) 
    n^2 for the loops 
    d for finding the similarity between D[i] and D[j] 

разреженных матриц форма создания Simiarity матрицы

for i in range(0,n): 
    for j in range(0,n): 
     if S[i,j]==0: 
      continue 
     else 
      insert into sparse_matrix [i, j, S[i,j]] 

The above runs in O(n^2) 
    n^2 for the loops 

Выполнение как операция требует O (N^2 г) + О (n^2), если делать один за другим.

Поскольку нам требуется только разреженная матрица, мы создаем разреженную матрицу напрямую, не создавая матрицу подобия.

Создание разреженной матрицы непосредственно без создания матрицы подобия:

for i in range(0,n): 
    for j in range(0,n): 
     find similarity_val of D[i] and D[j] 
     if similarity_val==0: 
      continue 
     else 
      insert into sparse_matrix [i,j,similarity_val] 

Мой вопрос:

Wouldn't the above run in only O(n^2 d), since I am directly inserting into sparse matrix 
    n^2 for the two loops 
    d for finding the similarity_val of D[i] and D[j] 

Пожалуйста, дайте мне знать, если я что-то отсутствует или мое понимание чего-то не так.

Answer 1

Для каждой пары (i, j) (всего n^2) вы достигаете внутренней части цикла, где вы находите сходство, а затем условно добавляете элементы в свою разреженную матрицу. Поиск сходства принимает операции «d» (потому что вам нужно прокручивать каждое из ваших измерений), и условное добавление элемента принимает постоянное число операций (либо 1 операция сравнения в случае, когда значение равно 0 и 1 операция сравнения плюс одна вставка в случае, когда значение отличное от нуля). Поскольку вам нужно делать «d» плюс постоянное количество операций каждый раз, когда вы достигаете внутренней части этого двойного цикла, в целом вы выполняете операции O (n^2 d).

Обратите внимание, что этот счет асимптотической операции не изменится, если вы ограничиваете внутренний цикл значениями j, которые не меньше i (aka замените for j in range(0, n) на for j in range(i, n)). Это связано с тем, что вы достигнете внутренней части цикла n * (n + 1)/2 раза и выполните «d» плюс постоянное количество операций, которое по-прежнему равно O (n^2 d).