当前位置: 首页 > >

数据结构与算法 第1.1章 C语言

发布时间:

代码速率的比较

我们使用time.h头文件中的clock()函数,可以捕捉从程序开始到clock()被调用时所消耗的时间,时间单位是clock tick,即“时钟打点”在C和C++中定义的类型是clock_t。同时,还有一个常数CLK_TCK,给出了机器时钟每秒所走的时钟打点数。


#include
#include

clock_t start, stop;
double duration;

int main(void)
{
start = clock();
MyFunction();
stop = clock();
duration = ((double)(stop-start))/CLK_TCK;

return 0;
}

下面用一个具体的多项式函数的数值计算来比较秦九韶与直接法的效率差别。令

f(x)=∑9i=0i×xi



f


(


x


)


=







i


=


0



9



i


×



x


i


,计算

f(1.1)



f


(


1.1


)


#include
#include
#include

clock_t start, stop;
double duration;
#define MAXN 10
#define MAXK 1e7

double f1(int n, double a[], double x)
{
int i;
double p = a[0];
for(i = 1; i <= n; i++)
p += (a[i]*pow(x,i);
return p;
}
double f2(int i, double a[], double x)
{
int i;
double p = a[0];
for(i = n; i > 0; i--)
p = a[i-1]+x*p;
return p;
}

void run(double(*f)(int, double*, double), double a[], int case_n)
{
int i;

start = clock();
for(i = 0;i < MAXK; i++)
(*f)(MANN-1, a, 1.1);
stop = clock();


duration = ((double)(stop-start))/CLK_TCK;
printf("ticks%d=%f
", case_n, (double)(stop-start));
printf("duration%d=%6.2e
", case_n, duration);
}
int main(void)
{
int i;
double a[MAXN];
a[i] = (double)i;

run(f1, a, 1);
run(f2, a, 2);
return 0;
}

注意,在程序中的run函数中,被测函数(*f)作为参数传入。


最大子列数(理解算法的复杂度)

问题:给定n个整数的序列

{a1,a2,...,an}



{



a


1



,



a


2



,


.


.


.


,



a


n



}

,求函数

f(i,j)=max{0,∑jk=iak}



f


(


i


,


j


)


=


m


a


x


{


0


,







k


=


i



j




a


k



}

的最大值。
[算法1.1]穷举法


int MaxSubseqSum1(int List[], int N)
{
int i, j, k;
int ThisSum, MaxSum = 0;
for(i = 0; i < N; i++){
for(j = i; j < N; j++)
ThisSum = 0;
for(k = i; k <= j; K++)
ThisSum += List[k];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}

从上面的代码中可以看出,时间复杂度是由3层嵌套的佛如循环决定的。





T(N)=∑i=1N∑j=iN∑k=1j1=O(N3)



T


(


N


)


=







i


=


1



N








j


=


i



N








k


=


1



j



1


=


O


(



N


3



)




注意到,内层的k循环涉及大量重复计算,是最大的浪费点。由于对于固定的i,当j增大了1之后,k循环要重新从i加到j。而实际上,第j-1步的计算结果可以直接存储下来,第j步只需要在此基础上累加一个List[j]就可以了,没有必要再从头加起。于是就有了一下的改进算法。


[算法1.2]:部分存储中间值的穷举法


int MaxSubseqSum2(int List[],int N)
{
int 1,j;
int ThisSum, MaxSun = 0;
for(i = 0; i< N;i++){
ThisSum = 0;
for(j = i; j < N; j++){
ThisSum += List[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}

此程序的时间复杂度是由2层嵌套的for循环决定的,算法复杂度降低到

O(N2)



O


(



N


2



)


[算法1.3]分而治之
我们可以将问题理解为:将序列一分为二,那么最大子列或者在左半边、或者在右半边、或者是横跨中分线的一段。分治法简要概述为:
第一步:将序列分为两个子序列;
第二步:递归求得最大和S左 和S右;
第三步:从中点分头向左右两边扫描,找出跨国分界线的最大子列和S中;
第四步:S_max = max{S左, S右, S中}


int Max3(int A, int B, int C)
{
return A>B?A>C?A:C:B>C?B:C;
}
int DivideAndConquer(int List[], int left, int right)
{
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum,MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int center, i;
if(left==right){
if(List[left]>0 return List[left];
else return0;
}
center = (left+right)/2;
MaxLeftSum = DivideAndConquer(List,left,right);
MaxRightSum = DivideAndConquer(List, center+1; right);
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for(i = center;i>=left;i--){
LeftBorderSum += List();
if(LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxLRightBorderSum = 0;
RightBorderSum = 0;
for(i = center+1;i<=right;i++){
RightBorderSum += List();
if(RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
return Max3(MaxLeftSum,MAxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}
int MaxSubseqSum3(int List[], int N)
{
return DivideAndConquer(List, 0, N-1);
}

我们使用MaxSubseqSum3将DivideAndConquer函数进行了包装,通过包装,我们输入的参数是不变的。
算法1.3的复杂度不好计算:若记整体的时间复杂度为

T(N)



T


(


N


)

,则函数DivideAndConquer中递归进行“分”的复杂度为

2T(N/2)



2


T


(


N



/



2


)

,因为我们解决了两个长度减半的子问题。求跨分界线的最大子列和时,有两个简单的for循环,所用的步骤一共不超过N,所以可以在

O(N)



O


(


N


)

时间完成。其他步骤都只需常数时间

O(1)



O


(


1


)


综上,有递推式:





T(1)=O(1);T(N)=2Y(N/2)+O(N)=2[2T((N/2)/2)+O(N/2)]+O(N/2)=22T(N/22)+2?O(N)=...=2kT(N/2)+k?O(N)



T


(


1


)


=


O


(


1


)


;



T


(


N


)


=


2


Y


(


N



/



2


)


+


O


(


N


)



=


2


[


2


T


(


(


N



/



2


)



/



2


)


+


O


(


N



/



2


)


]


+


O


(


N



/



2


)



=



2


2



T


(


N



/




2


2



)


+


2


?


O


(


N


)



=


.


.


.


=



2


k



T


(


N



/



2


)


+


k


?


O


(


N


)




当我们不断对分直到



N/2k=1



N



/




2


k



=


1

,即



2k=N




2


k



=


N

时,就得到



T(N)=N?T(1)+logN?O(N)=O(NlogN)



T


(


N


)


=


N


?


T


(


1


)


+


log


?


N


?


O


(


N


)


=


O


(


N


log


?


N


)




[算法1.4]:在线处理

在线的意思是每输入一个数据九进行及时处理,得到结果是对于当前已经读入的所有数据都成立的解,即任何一个地方终止输入,算法都能给出正确的当前解。


int MaxSubseqSum4(int List[], int N)
{
int i;
int ThisSum, MaxSum;
ThisSum = MaxSum = 0;
for(i = 0;i ThisSum += List[i];
if(ThisSum>MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}

算法只有一个for循环,复杂度只有

O(N)



O


(


N


)

,但是算法的正确性却不是那么显而易见。
这种算法并不要求存储序列中的数据,只需要将数字一个一个读入,同时一个一个地处理即可,处理过的数据没必要存起来。整个算法只要将输入数据扫描一遍,应该是我们可以达到的最快算法了。



友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网