UC知道算法分析疑惑题.........
来源：百度知道 编辑：UC知道 时间：2024/06/25 08:37:31
第一题：
void diff(int a[],int b[],int c[],int m,int n,int *ct)
{int i,j,exist,*ct=0;
{ for(i=0;i<m;i++)
exist=0;
for(j=0;j<n;j++)
if(a[i]==b[j])
{
exist=1;
break;
}
if(!exist) c[(*ct)++]=a[i];
}
}
问：把a和b看成两个整数集合（a和b中的整数都是两两不等），diff对a和b做了甚么运算？diff函数算法的时间复杂度为多少？
第二题:
void ins(int a[],int b[],int m,int n,int c[],int *ct)
{int i=j=0,*ct=0;
while(i<m&&j<n)
if(a[i]==b[j])
{ c[(*ct)++]=a[i];i++;j++;
}
else
if(a[i]<b[j])
i++;
else j++;
}
问：整数集合A的m个元素按由小到大的次序存储在数组a中，整数集合B的n个元素按由小到大的次序存储在数组b中。指出以上函数的功能及其算法的时间复杂度（设m>n）。
对 是{ exist=0;
void diff(int a[],int b[],int c[],int m,int n,int *ct)
{int i,j,exist,*ct=0;
{ for(i=0;i<m;i++)
exist=0;
for(j=0;j<n;j++)
if(a[i]==b[j])
{
exist=1;
break;
}
if(!exist) c[(*ct)++]=a[i];
}
}
问：把a和b看成两个整数集合（a和b中的整数都是两两不等），diff对a和b做了甚么运算？diff函数算法的时间复杂度为多少？
第二题:
void ins(int a[],int b[],int m,int n,int c[],int *ct)
{int i=j=0,*ct=0;
while(i<m&&j<n)
if(a[i]==b[j])
{ c[(*ct)++]=a[i];i++;j++;
}
else
if(a[i]<b[j])
i++;
else j++;
}
问：整数集合A的m个元素按由小到大的次序存储在数组a中，整数集合B的n个元素按由小到大的次序存储在数组b中。指出以上函数的功能及其算法的时间复杂度（设m>n）。
对 是{ exist=0;
第一题是做A-B的集合运算(假设a[]是集合A,b[]是集合B,把结果存在c[]里)
第二题本意应该是算A和B的交集,但是有缺陷,考虑a[]={1,2,3,4,5}和b={4,1,5,2,3}这种情况
至于复杂度,答案就是anshun93同学说的那样
另外第一题里的第一个for的大括号是不是没写对地方?
第一题
提取出a[]中,b[]没有的数,放入c[].
说起来有点饶口,其实就是,c[]的数全都属于a[],但c[]中找不出任何一个数和b[]中任何一个数相等.怎么感觉还是很饶口啊!哎~~,算了,能理解就成.
还有
{ for(i=0;i<m;i++)
exist=0;
这段错了
应该是这样的
for(i=0;i<m;i++)
{exist=0;
第二题
提取出a[]和b[]的交集放入c[],并由小到大排列.
至于复杂度这东西,说实话,我一直不理解是啥玩意,所以就不好回答你了.
第一题的算法复杂度是O(MN)；第二题的是O(M)。