算法 数据结构——用C语言描述（期末复习1）

//为什么一贴代码就卡死了
1

算法+数据结构=程序

首先，我们来了解一下，什么是算法
算法：规则的有限集合，为解决特定问题规定的一系列操作。
说白了就是解决问题的方法。
特性：

1. 有限性：有生之年解决。
2. 确定性：无歧义，意思明确。
3. 可行性：能搞！
4. 输入：可以有0个。
5. 输出：至少有1个。

在有限（有限）的时间里，确定（确定）下来一个能干（可行）的事情，可以不开始（输入），但必须结束（输出）。（胡说）

知道了什么是算法，然后看看我们设计算法需要注意什么。

算法设计的要求

1. 算法的正确性：对输入的数据能够得出满足要求的结果，一般只需要算法做到对精心选择的典型，苛刻而带有刁难性的输入数据得到结果。

2. 可读性：便于人们理解和相互交流。

3. 健壮性（鲁棒性）：对非法数据加以识别并处理，而不是产生错误动作或瘫痪。（好好锻炼变强壮了才能提高免疫力）

4. 高效率和低存储量：越快，占用储存空间越少越好。

好了，到这里，我们已经设计了一个算法，然后，我们需要对他进行评价，看看他到底行不行。 首先，我们来进行算法的时间性能分析 我们先了解一个叫语句频度的东西。
语句频度：该语句在一个算法中重复执行的次数。一个算法的时间耗费就是该算法中所有的语句频度的和。

#define n 100            

void M(int a[n] [n],int b[n][n],int c[n][n])

{

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

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

   {

      c[i][j]=0;                              n*n

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

           c[i][j]=c[i][j]+a[i][j]*b[i][j];      n*n*n

   }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

频度之和为f(n)=2nnn+3n*n+2n+1.
然后是算法的时间复杂度

T(n)=O(f(n)) （O表示数量级。）
例1.4 常数阶表示

temp=i;
i=j;
j=temp;
1
2
3

T(n)=O(1),算法时间复杂度为O(1).
例1.5 线性阶表示

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

时间复杂度为O(n)

例1.6 平方阶表示

x=0;y=0;
for(k=1;k<=n;k++)
x++;
for(i=0;i<=n;i++)
for(j=1;j<=n;j++)
y++;
1
2
3
4
5
6

f(n)=n*n/2+n/2;
T(n)=O(f(n))=O(n^2)

到了这里，我们要考虑最坏时间复杂度的问题了，也就是最坏情况下的时间复杂度。这东西可以保证算法的最长运行时间，使时间不会超过这个上界。

时空时空，时间说完了，然后是空间。
算法的空间性能分析
1.算法耗费的空间：计算整个辅助空间单元个数。
2.空间复杂度：S(n)=O(f(n))
如
例1.9
算法1

for(i=0;i<n;i++)
b[i]=a[n-i-1];
for(i=0;<n;i++)
a[i]=b[i];
1
2
3
4

算法2

for(i=0;i<n/2;i++)
{
  t=a[i];
  a[i]=a[n-i-1];
  a[n-i-1]=t;
}
1
2
3
4
5
6

算法1的空间复杂度为O(n),需要一个大小为n的辅助数组b。
算法2的空间复杂度为O(1),仅需要1个变量t，与问题规模没关系。

好多大神们想出来的算法摆在我们面前，我们要怎么选择这些算法呢？
算法性能选择;
1.若该程序使用次数少，则力求算法简明易懂。
2.对于反复运用的程序，尽可能选择快速的算法。
3.若待解决问题数据量极大，计算机储存空间较小，则算法应主要考虑如何节省空间。

//看到这里了，留个赞怎么样（疯狂暗示）
1