9 个解决方案
#1
序列a和b是否有序？组成新的有序排列是否存放在新的序列c中还是在a或者b中插入？
若a和b都有序，那么比较a,b中起始数字的大小（若按照小到大排列），取出其中较小
的数字所在的数组（设为a），将该数字赋给新的数组第一个，再取a的第二个数字将其
和数组b中第1个相比较....具体算法如下：
int a[10],b[12],c[22];
int i,j,k;
i=j=k=0;
void insert()
{
do {
if a[i]<b[j]
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=b[j];
j++;
k++;
}
}while (i<=10&&j<=12);
if i<10
{
for (j=i+1;j<10;j++)
{
c[k]=a[j];
k++;
}
if j<12
{
for (i=j+1;i<10;i++)
{
c[k]=b[j];
k++;
}
}
本算法的时间复杂度：O(n)
若a和b都有序，那么比较a,b中起始数字的大小（若按照小到大排列），取出其中较小
的数字所在的数组（设为a），将该数字赋给新的数组第一个，再取a的第二个数字将其
和数组b中第1个相比较....具体算法如下：
int a[10],b[12],c[22];
int i,j,k;
i=j=k=0;
void insert()
{
do {
if a[i]<b[j]
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=b[j];
j++;
k++;
}
}while (i<=10&&j<=12);
if i<10
{
for (j=i+1;j<10;j++)
{
c[k]=a[j];
k++;
}
if j<12
{
for (i=j+1;i<10;i++)
{
c[k]=b[j];
k++;
}
}
本算法的时间复杂度：O(n)
#2
struct nc {
nc *next;
int num;
};
main()
{
nc *p,*q,*r;
p = nc;//p指向c链表头;
q = na;//q指向a链表头;
while(na!=0)
{
if(p == 0)//头一个结点
{
nc = q;
na = na->next;
q = na;
}
else
{
while(p->next != 0 && q->num > p->num)
{
r = p;
p = p->next;
}
if(r == 0)//q结点的num小于c链表的第一个结点
{
na = na->next;
q->next = p;
nc = q;
}
if(q->num>p->num)//最后一个结点
{
p->next = q;
na = na->next;
q = na; //q始终跟踪na第一个结点;
}
else//一个中间结点
{
r->next = q;
na = na->next;
q->next = p;
q = na;
}
}
}
}
以上部分是对na链表排序,实际程序是对na排序,再对nb排序,然后将两个排好序的链表相连就得到你要的结果,下面分析时间复杂度.
最好的情况下:
从a链表取一个结点就插入到c链表的链表头,这时只要na次,b表也是同样所以要nb次,相加就是n次.
最坏的情况下就是每取一个结点要比较(nc中的结点个数)次也就是0,1,2,......n-1也就是(n-1).(n-2)/2吧.
但是好像求平均时间复杂度要用到概率的东西,我不是太懂(当初没有学好啊,好后悔啊),不好意思:)
nc *next;
int num;
};
main()
{
nc *p,*q,*r;
p = nc;//p指向c链表头;
q = na;//q指向a链表头;
while(na!=0)
{
if(p == 0)//头一个结点
{
nc = q;
na = na->next;
q = na;
}
else
{
while(p->next != 0 && q->num > p->num)
{
r = p;
p = p->next;
}
if(r == 0)//q结点的num小于c链表的第一个结点
{
na = na->next;
q->next = p;
nc = q;
}
if(q->num>p->num)//最后一个结点
{
p->next = q;
na = na->next;
q = na; //q始终跟踪na第一个结点;
}
else//一个中间结点
{
r->next = q;
na = na->next;
q->next = p;
q = na;
}
}
}
}
以上部分是对na链表排序,实际程序是对na排序,再对nb排序,然后将两个排好序的链表相连就得到你要的结果,下面分析时间复杂度.
最好的情况下:
从a链表取一个结点就插入到c链表的链表头,这时只要na次,b表也是同样所以要nb次,相加就是n次.
最坏的情况下就是每取一个结点要比较(nc中的结点个数)次也就是0,1,2,......n-1也就是(n-1).(n-2)/2吧.
但是好像求平均时间复杂度要用到概率的东西,我不是太懂(当初没有学好啊,好后悔啊),不好意思:)
#3
//复杂度为O(log(na)*na)+O(log(nb)*nb)+O(na+nb)
#include <algorithm>
typedef int type;
const int na = 100;
const int nb = 100;
main()
{
type a[na]={……};
type b[nb]={……};
type out[na+nb];
std::sort(a,a+na);
std::sort(b,b+nb);
std::merge(a,a+na,b,b+nb,out);
}
#include <algorithm>
typedef int type;
const int na = 100;
const int nb = 100;
main()
{
type a[na]={……};
type b[nb]={……};
type out[na+nb];
std::sort(a,a+na);
std::sort(b,b+nb);
std::merge(a,a+na,b,b+nb,out);
}
#4
我的意思是说在a和b排好序后，在将他们合并成一个有序序列的时间复杂度，其最好情况下是0(min(na,nb)),最坏情况下是0(na+nb)；当时如果na和nb相差较大时，其平均复杂度是多少？
#5
不对吧，如果a，b都排好序，那么最好应是1次阿，比较一下a最大的，如果比b最小的小，就将a，b直接连接。
#6
你好像没有具体算法把，如果有具体算法才有算法的时间复杂度，如果没有具体算法，个人的时间复杂度都是不同的，请三思
#7
如论最好最坏复杂度都是O(na+nb)呀，你总得对所有的数过一遍吧！这就是说最好也要O(na+nb),幸好只要过一遍就OK所以最坏也是O(na+nb)
#8
就是O(na+nb)
#9
老大们
O(na+nb)与O(n)难道有区别吗?
O(na+nb)与O(n)难道有区别吗?
#1
序列a和b是否有序？组成新的有序排列是否存放在新的序列c中还是在a或者b中插入？
若a和b都有序，那么比较a,b中起始数字的大小（若按照小到大排列），取出其中较小
的数字所在的数组（设为a），将该数字赋给新的数组第一个，再取a的第二个数字将其
和数组b中第1个相比较....具体算法如下：
int a[10],b[12],c[22];
int i,j,k;
i=j=k=0;
void insert()
{
do {
if a[i]<b[j]
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=b[j];
j++;
k++;
}
}while (i<=10&&j<=12);
if i<10
{
for (j=i+1;j<10;j++)
{
c[k]=a[j];
k++;
}
if j<12
{
for (i=j+1;i<10;i++)
{
c[k]=b[j];
k++;
}
}
本算法的时间复杂度：O(n)
若a和b都有序，那么比较a,b中起始数字的大小（若按照小到大排列），取出其中较小
的数字所在的数组（设为a），将该数字赋给新的数组第一个，再取a的第二个数字将其
和数组b中第1个相比较....具体算法如下：
int a[10],b[12],c[22];
int i,j,k;
i=j=k=0;
void insert()
{
do {
if a[i]<b[j]
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=b[j];
j++;
k++;
}
}while (i<=10&&j<=12);
if i<10
{
for (j=i+1;j<10;j++)
{
c[k]=a[j];
k++;
}
if j<12
{
for (i=j+1;i<10;i++)
{
c[k]=b[j];
k++;
}
}
本算法的时间复杂度：O(n)
#2
struct nc {
nc *next;
int num;
};
main()
{
nc *p,*q,*r;
p = nc;//p指向c链表头;
q = na;//q指向a链表头;
while(na!=0)
{
if(p == 0)//头一个结点
{
nc = q;
na = na->next;
q = na;
}
else
{
while(p->next != 0 && q->num > p->num)
{
r = p;
p = p->next;
}
if(r == 0)//q结点的num小于c链表的第一个结点
{
na = na->next;
q->next = p;
nc = q;
}
if(q->num>p->num)//最后一个结点
{
p->next = q;
na = na->next;
q = na; //q始终跟踪na第一个结点;
}
else//一个中间结点
{
r->next = q;
na = na->next;
q->next = p;
q = na;
}
}
}
}
以上部分是对na链表排序,实际程序是对na排序,再对nb排序,然后将两个排好序的链表相连就得到你要的结果,下面分析时间复杂度.
最好的情况下:
从a链表取一个结点就插入到c链表的链表头,这时只要na次,b表也是同样所以要nb次,相加就是n次.
最坏的情况下就是每取一个结点要比较(nc中的结点个数)次也就是0,1,2,......n-1也就是(n-1).(n-2)/2吧.
但是好像求平均时间复杂度要用到概率的东西,我不是太懂(当初没有学好啊,好后悔啊),不好意思:)
nc *next;
int num;
};
main()
{
nc *p,*q,*r;
p = nc;//p指向c链表头;
q = na;//q指向a链表头;
while(na!=0)
{
if(p == 0)//头一个结点
{
nc = q;
na = na->next;
q = na;
}
else
{
while(p->next != 0 && q->num > p->num)
{
r = p;
p = p->next;
}
if(r == 0)//q结点的num小于c链表的第一个结点
{
na = na->next;
q->next = p;
nc = q;
}
if(q->num>p->num)//最后一个结点
{
p->next = q;
na = na->next;
q = na; //q始终跟踪na第一个结点;
}
else//一个中间结点
{
r->next = q;
na = na->next;
q->next = p;
q = na;
}
}
}
}
以上部分是对na链表排序,实际程序是对na排序,再对nb排序,然后将两个排好序的链表相连就得到你要的结果,下面分析时间复杂度.
最好的情况下:
从a链表取一个结点就插入到c链表的链表头,这时只要na次,b表也是同样所以要nb次,相加就是n次.
最坏的情况下就是每取一个结点要比较(nc中的结点个数)次也就是0,1,2,......n-1也就是(n-1).(n-2)/2吧.
但是好像求平均时间复杂度要用到概率的东西,我不是太懂(当初没有学好啊,好后悔啊),不好意思:)
#3
//复杂度为O(log(na)*na)+O(log(nb)*nb)+O(na+nb)
#include <algorithm>
typedef int type;
const int na = 100;
const int nb = 100;
main()
{
type a[na]={……};
type b[nb]={……};
type out[na+nb];
std::sort(a,a+na);
std::sort(b,b+nb);
std::merge(a,a+na,b,b+nb,out);
}
#include <algorithm>
typedef int type;
const int na = 100;
const int nb = 100;
main()
{
type a[na]={……};
type b[nb]={……};
type out[na+nb];
std::sort(a,a+na);
std::sort(b,b+nb);
std::merge(a,a+na,b,b+nb,out);
}
#4
我的意思是说在a和b排好序后，在将他们合并成一个有序序列的时间复杂度，其最好情况下是0(min(na,nb)),最坏情况下是0(na+nb)；当时如果na和nb相差较大时，其平均复杂度是多少？
#5
不对吧，如果a，b都排好序，那么最好应是1次阿，比较一下a最大的，如果比b最小的小，就将a，b直接连接。
#6
你好像没有具体算法把，如果有具体算法才有算法的时间复杂度，如果没有具体算法，个人的时间复杂度都是不同的，请三思
#7
如论最好最坏复杂度都是O(na+nb)呀，你总得对所有的数过一遍吧！这就是说最好也要O(na+nb),幸好只要过一遍就OK所以最坏也是O(na+nb)
#8
就是O(na+nb)
#9
老大们
O(na+nb)与O(n)难道有区别吗?
O(na+nb)与O(n)难道有区别吗?