设二维数组a[1…m, 1…n] 含有m*n 个整数。
① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no);
② 试分析算法的时间复杂度。
①[题目分析]
判断二维数组中元素是否互不相同,只有逐个比较,找到一对相等的元素,就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次?在当前行,每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p的for循环),然后同第i+1行及以后各行元素比较一次,这就是循环控制变量k和p的二层for循环。
[算法描述]
int JudgEqual(ing a[m][n],int m,n) {
//判断二维数组中所有元素是否互不相同,如是,返回1;否则,返回0。
for(i=0;i<m;i++)
for(j=0;j<n-1;j++){
for(p=j+1;p<n;p++) //和同行其它元素比较
if(a[i][j]==a[i][p]){
cout<<"no";
return(0);
}
//只要有一个相同的,就结论不是互不相同
for(k=i+1;k<m;k++) //和第i+1行及以后元素比较
for(p=0;p<n;p++)
if(a[i][j]==a[k][p]){
cout<<"no";
return(0);
}
}// for(j=0;j<n-1;j++)
cout<<"yes";
return(1); //元素互不相同
}//算法JudgEqual结束
② 二维数组中的每一个元素同其它元素都比较一次,数组*mn个元素,第1个元素同其它mn-1个元素比较,第2个元素同其它mn-2 个元素比较,……,第mn-1个元素同最后一个元素(mn)比较一次,所以在元素互不相等时总的比较次数为 (mn-1)+(mn-2)+…+2+1=(mn)(mn-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(mn-1)个位置上均可能相同,这时的平均比较次数约为(mn)(mn-1)/4,总的时间复杂度是O(n4)。