设二维数组 a[1..m, 1..n] 含有 m*n 个整数。试分析算法的时间复杂度。
二维数组中的每一个元素同其它元素都比较一次，数组中共 m*n 个元素，第 1 个元素同其它 m*n-1 个元素比较，第 2 个元素同其它 m*n-2 个元素比较，……，第 m*n-1 个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为 (m*n-1)+(m*n-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4，总的时间复杂度是 O(n4 )。
举一反三
- 算法设计题(5)设二维数组a[1..m,1..n]含有m*n个整数。1写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no);2试分析算法的时间复杂度。
- 设数组a[1..m，1..n]（m＞1，n＞1）中的元素按行存放，每个元素占用1个存储单元，则数组元素a[i,j]（1≤i≤m，1≤j≤n）相对于数组首元素的偏移量为（）。 A: （i－1）×m＋j－1 B: （i－1）×n＋j－1 C: （j－1）×m＋i－1 D: （j－1）×n＋i－1
- 设n个不同的整数按升序存于数组A[1..n]中,设计分治算法求使得A[i]=i的下标i,并分析时间复杂度。[/i]
- 设计一个算法，将含有n个元素的数组A的元素A[0..n-1]循环右移m位，要求算法的空间复杂度为O(1)。
- 设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为（）。 A: （i-1）*n+j B: （i-1）*n+j-1 C: i*（j-1） D: j*m+i-1
内容
- 0
设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[i,j],在一维数组B中的下标为( )。 A: (i-j)*n+j B: (i-1)*n+j-1 C: i*(j-1) D: j*m+i-1
- 1
设有一个m行n列矩阵存储在二维数组A[1..m，1..n]中，将数组元素按行排列，则对于A[i，j]（1<=i<=m），1<=j<=n），排列在其前面的元素个数为（） A: i*（n-1）+j B: （i-1）*n+j-1 C: i*（m-1）+j D: （i-1）*m+j-1
- 2
设二维数组A[1…m,1…n]（即m行n列）按行存储在B[1…m*n]中，则二维数组元素A[i,j]在一位数组B中的下标为
- 3
【算法设计题】设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。
- 4
设有一个m行n列的矩阵存储在二维数组A[1．．M,1．．n]中，将数组元素按行排列，对于A[i,j]（1≤i≤m，l≤j≤n)，排列在其前面的元素个数为（）。 A: i*(n-1)+j B: (i-1)*n+J-1 C: i*(m-l)+j D: (i-1)*m+J-1