Question

跪求C语言数据结构大神，时间复杂度和空间复杂度如何计算，以我给的大整数加法（无符号）运算为例

int unsigndeadd(lnodelist &ahead,lnodelist &bhead)//无符号大整数的加法
{
int sum,carry=0; //进位
lnode *pa,*pb;
lnode *p,*chead;
pa=ahead->next; //令pa指向数a中头结点的下一个结点
pb=bhead->next; //令pb指向数b中头结点的下一个结点
p=chead=(lnode *)malloc(sizeof(lnode));//分配内存
p->data=0;
p->next=p;
p->prior=p; //初始化用于存储计算结果的链表
while(pa!=ahead&&pb!=bhead) //若pa和pb均未指向各自对应的头结点则执行循环
{ sum=pa->data+pb->data+carry;//sum存储papb各自指向结点数据域数值之和并再加上carry
p=(lnode *)malloc(sizeof(lnode));
p->data=sum%10000; //建立并令p指向结点数据域存储sum除以10000的余数
carry = sum/10000; //carry值为sum整除10000后的数值,若大于0则进位
p->next=chead->next;
chead->next->prior=p;
chead->next=p;
p->prior=chead;//将p指向的结点插到头结点chead后面
pa=pa->next;
pb=pb->next; //指针pa及pb后移
}
if(pa!=ahead)
{while(pa!=ahead)//a还没有处理完，把a剩下的数字加到和上
{
sum=pa->data+carry; //sum存储pa指向结点数据域数值并再加上carry
p=(lnode *)malloc(sizeof(lnode)); //分配内存
p->data=sum%10000; //令p指向结点数据域存储sum除以10000的余数
p->next=chead->next;
chead->next->prior=p;
chead->next=p;
p->prior=chead; //将p指向的结点插到头结点chead后面
carry = sum/10000; //carry值该为sum整除10000后的数值
pa=pa->next; //指针pa后移
}
}
if(pb!=bhead)
{while(pb!=bhead)//b还没有处理完，把b剩下的数字加到和上
{
sum=pb->data+carry; //sum存储pb指向结点数据域数值并再加上carry
p=(lnode *)malloc(sizeof(lnode)); //分配内存
p->data=sum%10000; //令p指向结点数据域存储sum除以10000的余数
p->next=chead->next;
chead->next->prior=p;
chead->next=p;
p->prior=chead; //将p指向的结点插到头结点chead后面
carry = sum/10000; //carry值该为sum整除10000后的数值
pb=pb->next; //指针pb后移
}
}
if(carry)//如果最后一位有进位，就申请一个结点存储
{ p=(lnode *)malloc(sizeof(lnode)); //分配内存
p->data=carry; //令p指向结点数据域存储整数carry
p->next=chead->next;
chead->next->prior=p;
chead->next=p;
p->prior=chead; //将p指向的结点插到头结点chead后面
}
putoutc(chead); //输出表c存储的结果
return OK;
}

Answer 1

int unsigndeadd(lnodelist &ahead,lnodelist &bhead)//无符号大整数的加法 假设长度分别为m>n

{
int sum,carry=0; //进位 空间复杂度+2

lnode *pa,*pb;

lnode *p,*chead;

pa=ahead->next; //令pa指向数a中头结点的下一个结点 // 时+1

pb=bhead->next; //令pb指向数b中头结点的下一个结点 // 时+1
p=chead=(lnode *)malloc(sizeof(lnode));//分配内存 // 空+1

p->data=0; // 时+1
p->next=p; // 时+1
p->prior=p; //初始化用于存储计算结果的链表 // 时+1
while(pa!=ahead&&pb!=bhead) //若pa和pb均未指向各自对应的头结点则执行循环 // 时+9n 空+n

{ sum=pa->data+pb->data+carry;//sum存储papb各自指向结点数据域数值之和并再加上carry // 时+1
p=(lnode *)malloc(sizeof(lnode)); // 空+1
p->data=sum%10000; //建立并令p指向结点数据域存储sum除以10000的余数 // 时+1
carry = sum/10000; //carry值为sum整除10000后的数值,若大于0则进位 // 时+1
p->next=chead->next; // 时+1
chead->next->prior=p; // 时+1
chead->next=p; // 时+1
p->prior=chead;//将p指向的结点插到头结点chead后面 // 时+1
pa=pa->next; // 时+1
pb=pb->next; //指针pa及pb后移 // 时+1
}
if(pa!=ahead) // 时+1
{while(pa!=ahead)//a还没有处理完，把a剩下的数字加到和上 // 时+8(m-n) 空+n

{
sum=pa->data+carry; //sum存储pa指向结点数据域数值并再加上carry // 时+1
p=(lnode *)malloc(sizeof(lnode)); //分配内存 // 空+1
p->data=sum%10000; //令p指向结点数据域存储sum除以10000的余数 // 时+1
p->next=chead->next; // 时+1
chead->next->prior=p; // 时+1
chead->next=p; // 时+1
p->prior=chead; //将p指向的结点插到头结点chead后面 // 时+1
carry = sum/10000; //carry值该为sum整除10000后的数值 // 时+1
pa=pa->next; //指针pa后移 // 时+1
}
}
if(pb!=bhead)
{while(pb!=bhead)//b还没有处理完，把b剩下的数字加到和上
{
sum=pb->data+carry; //sum存储pb指向结点数据域数值并再加上carry
p=(lnode *)malloc(sizeof(lnode)); //分配内存
p->data=sum%10000; //令p指向结点数据域存储sum除以10000的余数
p->next=chead->next;
chead->next->prior=p;
chead->next=p;
p->prior=chead; //将p指向的结点插到头结点chead后面
carry = sum/10000; //carry值该为sum整除10000后的数值
pb=pb->next; //指针pb后移
}
}
if(carry)//如果最后一位有进位，就申请一个结点存储 // 时+1
{ p=(lnode *)malloc(sizeof(lnode)); //分配内存 // 空+1
p->data=carry; //令p指向结点数据域存储整数carry // 时+1
p->next=chead->next; // 时+1
chead->next->prior=p; // 时+1
chead->next=p; // 时+1
p->prior=chead; //将p指向的结点插到头结点chead后面 // 时+1
}
putoutc(chead); //输出表c存储的结果 // 时+m
return OK;
}

时=O(n) 空=O(n)
其实上面标出后可以明显看出怎么估算时空复杂度，一般主要看循环，循环里面如果进行的操作和字符串长度有关，那么复杂度就高，如果只是固定的几次操作，复杂度一般都是O(n)

Answer 2

主要看循环!其次看循环内的执行语句！列出关于循环的表达式求解！