线性搜索算法如下:设A的n个元素都不相同.r已在A中的概率为p(0≤p≤1),并且当x在A中时,x等于A的每
线性搜索算法如下:
设A的n个元素都不相同.r已在A中的概率为p(0≤p≤1),并且当x在A中时,x等于A的每一个元素的可能性相等.试分析算法的平均时间复杂度.
线性搜索算法如下:
设A的n个元素都不相同.r已在A中的概率为p(0≤p≤1),并且当x在A中时,x等于A的每一个元素的可能性相等.试分析算法的平均时间复杂度.
设A的n个元素都不相同,证明下述算法产生的排列A[1],A[2],…,A[n]服从均匀分布:
Random Permute Array(A) //数组A[1..n]
1.for i←1 to n do
2.产生{i,i+1,…,n}上的均匀随机数k
3.交换A[i]与A[k]
这段程序能起到随机化输入,使其服从均匀分布的作用.比如,在快速排序算法的前面加上这段程序,就得到随机快速排序算法.
A.(Ⅰ)中向量个数必大于r
B.(Ⅰ)中任意r-1个向量必线性无关
C.(Ⅰ)中任意r个向量必线性无关
D.(Ⅰ)中任意r+1个向量必线性相关
设有常系数齐次线性微分方程组,A为二阶常数矩阵,记p=-trA,q=detA,设p2+q2≠0,试证
(1)当p>0且q>0时,零解渐近稳定;
(2)当p>0且q=0;或p=0且q>0时,零解渐近稳定;
(3)其它情形下零解都不稳定.
B.若对任意一组不全为零的数k1,k2,…,ks,都有k1α1+k2α2+…+ksαs≠0,则向量组α1,α2,…,αs线性无关
C.若向量组α1,α2,…,αs线性相关,则其中任意一个向量都可以用其余s-1个向量线性表示
D.若向量组α1,α2,…,αs线性相关,则对任意一组不全为零的数k1,k2,…,ks都有k1α1+k2α2+…+ksαs=0
(1)用cerr<<及exit(1)语句来终止执行并报告错误;
(2)用返回布尔值false,true来实现算法,以区别是正常返回还是错误返[回;
(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。
试讨论这3种方法各自的优缺点,并以你认为是最好的方式实现它。
证明下述结论:
设x(1),x(2)是LP的可行解集K={x|Ax=b,x≥0)的两个极点,则x(1)与x(2)相邻的充要条件是:A的列向量集{pi|xi(1)+xi(2)>0}线性相关,且存在指标l使{pj|xi(1)+xi(2)>0,i≠l)线性无关(xi(1),xi(2)分别表示x(1),x(2)的第i个分量)