计算稀疏矩阵的时间复杂度（二）

Question

我有一个 (nxd) 的数据集 (D)，其中 n=行数，d= 维数，我通过比较数据集的每一行创建相似矩阵 (S)(nxn) ( D) 然后将其转换为稀疏矩阵 (tx3) 其中 t 是对称相似度矩阵 (S) 的非零元素的个数

创建相似度矩阵的时间复杂度为 o(n^2d)，其中 d 是某个常量运算。转换稀疏矩阵的时间复杂度为 theta(n^2)

我的问题是：在创建相似性矩阵时，如果我执行检查"if the similarity value is "零“然后继续（继续）否则将其放入稀疏矩阵”。假设这样，我可以说从数据集 (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]

稀疏矩阵创建形式相似矩阵

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 d) +O(n^2)。

因为我们只需要 sparse_matrix，所以我们直接创建稀疏矩阵而不创建相似度矩阵。

直接创建稀疏矩阵而不创建相似矩阵：

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" 操作（因为你需要遍历每个维度）并且有条件地添加一个元素需要恒定数量的操作（在值为 0 的情况下进行 1 次比较操作和 1 次比较操作在值为非零的情况下加上一个插入操作）。由于每次到达此双循环内部时都需要执行 "d" 加上恒定数量的操作，因此总共执行 O(n^2 d) 操作。

请注意，如果您将内部循环限制为不小于 i 的 j 值（也就是将 for j in range(0, n) 替换为 for j in range(i, n)），则此渐近运算计数不会改变。这是因为你将到达循环内部 n*(n+1)/2 次并执行 "d" 加上恒定数量的操作，这仍然是 O(n^2 d) 总计算量。

计算稀疏矩阵的时间复杂度（二）

Computing time complexity of the sparse matrix (2)

r

matlab

matrix

sparse-matrix