数据结构3-4

有穷性

一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束， 且每一步都可在有穷时间内完成；

确定性

算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。 有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

可行性

一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基 本运算执行有限次来实现的。

输入

一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集 合。

输出

一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系 的量。

有穷性

haha()
{/*only a joke,do nothing.*/
}
main()
{printf("请稍等...您将知道世界的未日...");
while(1)
haha();
}

确定性

float average(int *a,int num)
{int i;long sum=0;
for(i=0;i<num;i++)
sum+=*(a++);
return sum/num;
}
main()
{int score[10]={1,2,3,4,5,6,7,8,9,0};
printf("%f",average(score,10);
}

可行性

输入

输出

getsum(int num)
{
int i,sum=0;
for(i=1;i<=num;i++)
sum+=i;
} /*无输出的算法没有任何意义，

算法正确性的四个层次

程序不含语法错误。

max(int a,int b,int c)
{
if (a>b)
{if(a>c) returnc;
else returna;
}
}

程序对于几组输入数据能够得出满足规格说明要求的结果。

max(int a,int b,int c)
{
if (a>b)
{if(a>c) return a;
else return c;
}
} /*8,6,7*/ /*9,3,2*/

程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得 出满足规格说明要求的结果。

max(int a,int b,int c)
{
if (a>b)
{if(a>c) return a;
else return c;
}
else
{if(b>c) return b;
else return c;
}
}

程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

算法一

算法二

在三个整数中求最大者

max(int a,int b,int c)
{if (a>b)
{if(a>c) return a;
else return c;
}
else
{if(b>c) return b;
else return c;
}/*无需额外存储空间，只需两次比较*/

max(int a[3])
{int c,int i;
c=a[0];
for(i=1;i<3;i++)
if (a[i]>c) c=a[i];
return c;
}
/*需要两个额外的存储空间，两次比较，至少一次赋值*/

/*共需5个整型数空间*/

求100个整数中最大者

同上的算法难写，难读

max(int a[100])
{int c,int i;
c=a[0];
for(i=1;i<100;i++)
if (a[i]>c) c=a[i];
return c;
}
/*共需102个整型数空间*/

程序在计算机上运行所需时间的影响因素

算法本身选用的策略

问题的规模

规模越大，消耗时间越多

书写程序的语言

语言越高级，消耗时间越多

编译产生的机器代码质量

机器执行指令的速度

求4*4矩阵元素 和，T(4)=O(f(4))

f=n*n;

sum(int num[4][4])

{ int i,j,r=0;
for(i=0;i<4;i++)

for(j=0;j<4;j++)

r+=num[i][j]; /*原操作*/

return r;
}

最好情况：
T（4）=O（0）

最坏情况：
T（4）=O（n*n）

ispass(int num[4][4])

{ int i,j;
for(i=0;i<4;i++)

for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+1)

return 0;

return 1;
}

语句

频度

时间复杂度

{++x;s=0;}

1

O(1)

for(i=1;i<=n;++i)

{++x;s+=x;}

n

O(n)

for(j=1;j<=n;++j)

for(k=1;k<=n;++k)

{++x;s+=x;}

n*n

O(n*n)

O(log n)

基本操作的执行次数不确定时的时间复杂度

平均时间复杂度

依基本操作执行次数概率计算平均

最坏情况下时间复杂度

在最坏情况下基本操作执行次数