矩阵乘法最naive的版本,自己数学弱爆了,矩阵乘法已经不知道怎么算了……
先科普下吧。
3 0 0 5
(A) 0 -1 0 0
2 0 0 0
乘
0 2
(B) 1 0
-2 4
0 0
首先乘出来的结果是,新矩阵的行是A的行,新矩阵的列是B的列。
计算方法是,首先A的第1行点乘(每个位置上分别乘)B第1列的元素,做为结果矩阵(1, 1)上的元素。然后A的第1行点乘第2列,做为结果矩阵(1, 2[......]
矩阵乘法最naive的版本,自己数学弱爆了,矩阵乘法已经不知道怎么算了……
先科普下吧。
3 0 0 5
(A) 0 -1 0 0
2 0 0 0
乘
0 2
(B) 1 0
-2 4
0 0
首先乘出来的结果是,新矩阵的行是A的行,新矩阵的列是B的列。
计算方法是,首先A的第1行点乘(每个位置上分别乘)B第1列的元素,做为结果矩阵(1, 1)上的元素。然后A的第1行点乘第2列,做为结果矩阵(1, 2[......]
矩阵在数值运算中很常见,本节关注如何存储矩阵的元,从而使矩阵的各种运算能有效进行。
如果矩阵中有许多相同值的元素或者很多零元素。有时为了节省存储空间,可以对这类矩阵进行存储压缩,称为稀疏矩阵。更进一步的,如果稀疏矩阵的相同值或零元素分布还是有规律的,我们可以称他们为特殊矩阵。
对称矩阵
例如:
1 2 4
2 3 5
4 5 6
我们可以为每一对称元分配一个存储空间,即可以将n^2个元压缩存储到n*(n+1)/2个空间中。
假设在线性(一元)数组中存储,下[......]
设:m是模式串pattern的长度,n是主串长度
传统的字符串匹配(暴力法)的时间复杂度是O(n*m)。
而KMP串匹配算法可以将时间复杂度降为O(n+m),这需要一个额外的预处理O(m)。
KMP优化的地方在于:当出现字符失配的情况时,无需回溯i指针,而是利用已经匹配的部分,将模式串尽可能向右滑动一部分。
实际上:KMP的预处理本身就是一个模式串pattern“自我匹配”的过程。因此,预处理和kmp算法主体非常神似。
预处理过程:
int get_next(ch[......]
字符串(string)是由零个或者多个字符串组成的有限序列。
字符串中字符的数目称为字符串的长度。
串中任意个连续字符组成的子序列称为改串的子串。包含子串的串相应地称为主串。
串相等:当且仅当两个串的长度相等,并且各个对应位置的字符都相等时。
由一个或者多个空格组成的串' '称为空格串,非空字符串!
C语言中的字符串最末尾是'\0',这个不用解释了。
串赋值StrAssign、串比较StrCompare、串求长StrLength、串连接StrConcat以及[......]
队列也可以用顺序存储表示。定义还是一样的:从队尾rear推入元素。从头部head拿出元素,是FIFO。
与链式存储一致,我们仍然需要附设两个指针front和rear分别表示队列头元素和队列元素的位置。初始时front=rear=0是队列空的条件。
每当插入新的队列元素时,尾指针将增1.删除队列头元素时,头指针增加1。即非空队列中:头元素总是指向队首元素,而尾指针总是指向队尾元素的下一个位置。
除了基本的顺序存储外,我们还可以使用循环数组来构造一个循环队列。
在循环队列中,[......]