题目内容
(请给出正确答案)
[主观题]
给定三个n×n矩阵A、B和C,下面的偏假1/2正确的蒙特卡罗算法用于判定AB=C.算法所需的计算时间为Q
给定三个n×n矩阵A、B和C,下面的偏假1/2正确的蒙特卡罗算法用于判定AB=C.
算法所需的计算时间为Q(n2).显然当AB=C时,算法Product(A,B,C,n)返回true.试证明当AB≠C时,算法返回值为false的概率至少为1/2(考虑矩阵AB-C并证明当AB≠C时,将该矩阵各行相加或相减最终得到的行向量至少有一半是非零向量).
如搜索结果不匹配,请 联系老师 获取答案