矩阵乘法结果的检验---Freivalds' algorithm
逛Uva的时候,看到了一个题,模型很简单,让验证一个矩阵是不是另一个矩阵的平方...朴素O(n^3)果断超时;看题解,原来是个随机算法-.-,思想和米勒拉宾素性测试很像,http://en.wikipedia.org/wiki/Freivalds'_algorithm
算法基于这么个事实:设X是一个随机向量,xi在{0,1,2...t}中任意选取;那么对于不同的矩阵A,B ,AX=BX的概率最多只有1/(t+1)
不严谨的证一下...
如果A != B ,而AX == BX 那必然有 (A-B)X==0 , 且 H=A-B != 0 ...
最坏情况呢...就是H的没个行向量都一样...就记为 h 吧, 既然非零,总有个hi != 0的
h1*x1+h2*x2+...+hn*xn==0 ==> xi=(h1*x1+...hi-1*xi-1+hi+1*xi+1+...hn*xn)/(-hi)
xi是0~t随机选的,他刚好满足这个条件的概率就是1/(t+1)...
那矩阵来乘个列向量,撑死是O(n^2)...做上几次测试,几乎就是必然了...更不必说那个1/(t+1)是个上界...