数据�l�构�W�五章算法设计题[8]_跨考网

1. 设二�l�数�l?/span>a[1..m, 1..n] 含有m*n 个整数�?/span>

　　(1) 写出���法(pascal�q�程�?/span>c函数)�Q�判�?/span>a中所有元素是否互不相同输出相关信�?/span>(yes/no)�Q?/span>

　　(2) 试分析算法的旉���复杂度。【华中理工大�?/span> 1999 �?/span> �Q?/span>10分）�?/span>

　　【参考答案�?/span>

　　[题目分析]判断二维数组中元素是否互不相同，只有逐个比较,扑ֈ�一对相�{�的元素�Q�就可结��Zؓ不是互不相同。如何达到每个元素同其它元素比较一�ơ且只一�ơ？在当前行�Q�每个元素要同本行后面的元素比较一�ơ（下面�W�一个��@环控制变�?/span>p�?/span>for循环�Q�，然后同第i+1行及以后各行元素比较一�ơ，�q�就是��@环控制变�?/span>k�?/span>p的二�?/span>for循环�?/span>

　　int JudgEqual(ing a[m][n],int m,n)

　　//判断二维数组中所有元素是否互不相同，如是�Q�返�?/span>1�Q�否则，�q�回0�?/span>

　　{for(i=0;i<m;i++)

　　for(j=0;j<n-1;j++)

　　{ for(p=j+1;p<n;p++) //和同行其它元素比�?/span>

　　if(a[i][j]==a[i][p]) {printf(�?/span>no�?/span>); return(0); }

　　//只要有一个相同的�Q�就�l�论不是互不相同

　　for(k=i+1;k<m;k++) //和第i+1行及以后元素比较

　　for(p=0;p<n;p++)

　　if(a[i][j]==a[k][p]) {printf(�?/span>no�?/span>); return(0); }

　　}// for(j=0;j<n-1;j++)

　　printf(yes�?/span>); return(1); //元素互不相同

　　}//���法JudgEqual�l�束

　　�Q?/span>2�Q�二�l�数�l�中的每一个元素同其它元素都比较一�ơ，数组中共m*n个元素，�W?/span>1个元素同其它m*n-1个元素比较，�W?/span>2个元素同其它m*n-2 个元素比较，……，�W?/span>m*n-1个元素同最后一个元�?/span>(m*n)比较一��?/span>,所以在元素互不相等时�ȝ��比较�ơ数�?/span> (m*n-1)+(m*n-2)+�?/span>+2+1=�Q?/span>m*n�Q?/span>(m*n-1)/2。在有相同元素时,可能�W�一�ơ比较就相同,也可能最后一�ơ比较时相同,讑֜�(m*n-1)个位�|�上均可能相�?/span>,�q�时的��^均比较次数约为（m*n�Q?/span>(m*n-1)/4�Q��ȝ��旉���复杂度是O(n4)�?/span>