题目内容
（请给出正确答案）
序列中元素A[i]和A[j]若满足i＜j且A[i]＞A[j]，则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort()，试证明：
a)若所有逆序对的间距均不超过k，则运行时间为o(kn);
b)特别地，当k为常数时，插入排序可在线性时间内完成;
c)若共有I个逆序对，则关键码比较的次数不超过o(I);
d)若共有I个逆序对，则运行时间为o(n+I)。
如果结果不匹配，请 联系老师 获取答案
更多“序列中元素A[i]和A[j]若满足i＜j且A[i]＞A[j]…”相关的问题
用Eij表示i行j列的元素为1，而其余元素全为零的nxn矩阵，A=(aij)nxn。证明：
1)如果AE12=E12A，那么当k≠1时ak1=0，当k≠2时a2k=0;
2)如果AEij=EijA，那么当k≠i时aki=0，当k≠j时ajk=0，且aii=ajj;
3)如果A与所有的n级矩阵可交换，那么A一定是数量矩阵，即A=aE。
可以按以下步骤证明矩阵的乘法满足结合律。
(i)设B=(bij)是一个nxp矩阵，令
是B的第j列，j=1，2，...，p，又设
是任意一个px1矩阵。证明：
(ii)设A是一个mxn矩阵，利用(i)及习题2的结果，证明：A(Bξ)=(AB)ξ。
(iii)设C是一个ρxq矩阵，利用(ii)证明：A(BC)=(AB)C。
设f(α，β)是n维线性空间V上的非退化对称双线性函数，对V中一个元素α，定义V*中一个元素α*：α*(β)=f(α，β)，β∈V。
试证：1)V到V*的映射α→α*是一个同构映射;
2)对V的每组基ε1，...，εn，有V的唯一的一组基ε1'，...，εn'使f(εi，εj')=δij;
3)如果V是复数域上n维线性空间，则有一组基η1，...，ηn，使ηi=ηi'，i=1，...，n。
使a和b在个一子集中当且仅当∈R,求证{A1,A2,...,Ak}是A的一个划分。
设在n阶行列式
中，aij=-aji(i，j=1，2，...，n)证明：当n是奇数时，D=0。
设
其中ai≠aj，当i≠j(i，j=1，2，...，n)。证明：与A可交换的矩阵只能是对角矩阵。
问题描述:机器人Rob在一个有n×n个方格的方形区域F中收集样本.(i,j)方格中样本的价值为v(i,j),如图3-6所示.Rob从方形区域F的左上角A点出发,向下或向右行走,
直到右下角的B点,在走过的路上,收集方格中的样本.Rob从A点到B点共走2次,试找出Rob的2条行走路径,使其取得的样本总价值最大.
算法设计:给定方形区域F中的样本分布,计算Rob的2条行走路径,使其取得的样本总价值最大.
数据输入:由文件input.xt给出输入数据.第1行有1个正整数n,表示方形区域F有n×n个方格.按下来每行有3个整数,前2个数表示方格位置,第3个数为该位置样本价值.最后一行是3个0.
结果输出:将计算的最大样本总价值输出到文件output.txt.
，k=0，1，2，...；aij=si+j-2，i，j=1，2，...，n。证明：
