c++ - 对称矩阵中的线性索引

标签 c++ algorithm matlab matrix

我们可以使用遵循这种模式的线性索引访问矩阵

0 1 2

3 4 5

6 7 8

对于这种情况很容易得到 i,j 坐标(n 是矩阵维数)。对于基于 0 索引的情况,它将是。

i = 索引/n

j = 指数 % n

现在,如果我的矩阵是对称的并且我只想访问上半部分怎么办

0 1 2 3

.. 4 5 6

..... 7 8

........ 9

我知道线性索引将由

指数 = j + n*i - i (i-1)/2

但我想知道给定 idx 的 i,j。你们知道这样做的任何方法吗?我在这里查了一下,但找不到答案。提前致谢。

最佳答案

如果你想使用你使用过的索引,并且你想避免循环,你可以反转索引的函数。我将使用 k 来表示线性索引,所有索引都是从零开始的。正如你所注意到的

k = j + n*i - i*(i-1)/2。

由于我们在这里使用的是正整数,而且所有组合 (i,j) 都映射到不同的 k 上这一事实意味着该函数是可逆的。我这样做的方式是首先注意

j = k - n*i + i*(i-1)/2

这样,如果您可以找到您所在的行,则该列由上述等式定义。现在考虑你想要的行,定义为

行=分钟{我| k - ni + i(i-1)/2 >= 0 }.

如果你求解二次方程 k - ni + i(i-1)/2 = 0 并取 i 的底数,这会得到行,即

行 = floor( (2n+1 - sqrt( (2n+1)^2 - 8k ) )/2 )

然后

j = k - 行 * n + 行 * (行-1)/2。

在伪代码中这将是

//Given linear index k, and n the size of nxn matrix
i = floor( ( 2*n+1 - sqrt( (2n+1)*(2n+1) - 8*k ) ) / 2 ) ;
j = k - n*i + i*(i-1)/2 ;

这消除了对循环的需要,并且对于大型矩阵会快很多

关于c++ - 对称矩阵中的线性索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19143657/

相关文章:

algorithm - 在matlab中创建离散阶跃函数

c++ - 使用有限的RAM运行C++程序

c++ - 如何将 QTableWidgetItem 转换为自定义子类

c++ - C++ 中的概念检查变化?

algorithm - 求解递归 T(n) = 2T(n/2) + sqrt(n)

algorithm - 快速排序时间复杂度最佳案例输入

matlab - 如何并行运行 Matlab 计算

c++ - Eclipse 字符集类似于 Visual C++

java - 在 C++ 和 Java 中只有一个返回值的原因是什么?

matlab - MATLAB GUIDE 中的按钮回调类型