求解一个算法的时间复杂度
N个数。有两个序列a和b,大小分别为na和nb，其中的数都是从N个数中随机取得，然后分别将两个序列排成有序序列。请问如果让你将这两个序列合并成一个有序序列，你如何做？你的算法的平均时间复杂度有时多少？ 问题点数：20、回复次数：9Top
1 楼hammer_shi（dmresearch）回复于 2002-04-23 09:24:18 得分 5
序列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)Top
2 楼ha_y（天之恒）回复于 2002-04-23 10:54:54 得分 5
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吧.
但是好像求平均时间复杂度要用到概率的东西,我不是太懂(当初没有学好啊,好后悔啊),不好意思:)Top
3 楼IT_worker（IT工人）回复于 2002-04-23 11:50:00 得分 5
//复杂度为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);
}Top
4 楼wtzyb4446（不死鸟）回复于 2002-04-23 13:19:48 得分 0
我的意思是说在a和b排好序后，在将他们合并成一个有序序列的时间复杂度，其最好情况下是0(min(na,nb)),最坏情况下是0(na+nb)；当时如果na和nb相差较大时，其平均复杂度是多少？Top
5 楼ha_y（天之恒）回复于 2002-04-23 14:55:49 得分 1
不对吧，如果a，b都排好序，那么最好应是1次阿，比较一下a最大的，如果比b最小的小，就将a，b直接连接。Top
6 楼ha_y（天之恒）回复于 2002-04-23 14:57:25 得分 1
你好像没有具体算法把，如果有具体算法才有算法的时间复杂度，如果没有具体算法，个人的时间复杂度都是不同的，请三思Top
7 楼IT_worker（IT工人）回复于 2002-05-07 08:45:54 得分 1
如论最好最坏复杂度都是O(na+nb)呀，你总得对所有的数过一遍吧！这就是说最好也要O(na+nb),幸好只要过一遍就OK所以最坏也是O(na+nb)Top
8 楼pz（平常人一个,一生力求做好"中庸"之道.）回复于 2002-05-07 19:51:37 得分 1
就是O(na+nb)
Top
9 楼Koorama（顺）回复于 2002-05-07 22:23:20 得分 1
老大们
O(na+nb)与O(n)难道有区别吗?Top
