【算法】算法初步

要学好数据结构和算法的设计与分析，请务必先打好C语言基础，因为C语言中的数据存储、内存映射、指针等等概念最接近计算机的底层原理，数据结构是数据在内存空间当中的组织形式，而算法则是提供了解决某个问题的一种思路，而数据结构与算法设计一定会涉及到最核心的部分：提升性能 —— 时间和空间的问题。如果有一个好的算法，它的执行时间很短，占用空间很小，数据结构的组织形式最优，这才是我们想要看见的结果。

算法为解决某个问题提供了一种思路，我们尝试让这种思路达到最优。

瑞士科学家沃思（N.Wirth）的著名公式：数据结构 + 算法 = 程序

C语言对内存的操作更加直观、方便、简洁，数据结构不过是数据在内存映射当中的组织形式，所以，透过C语言我们可以更加直接清晰的表达数据结构与算法的底层，C语言更接近计算机语言的底层。例如，在Java中，通过类对于数组、链表、栈等操作已经封装好了，虽然也可以使用但没有C语言直观的能看见数据在内存映射中的实际状态，所以我们尽可能都使用C语言来作为这门课的描述性语言。而且，根据不同的数据结构，我们将会采用不同的算法，在不同的应用场景中，算法的设计也不同。所以，我们使用C语言作为基础，因为对于一件事物的理解越接近底层离真相越近。

在我的资源中分别上传了两份资源：数据结构和算法（自整理），需要的朋友自取，（已经整理好了，直接使用文件中的内容掌握数据结构与算法这门课足够了）。

数据结构的概念

数据结构 （Data Structure）：数据结构指的是 数据元素及数据元素之间的相互关系，或组织数据的形式。 有人认为：按照某种逻辑关系组织起来的一批数据，应用计算机语言，按照一定的存取方式把它们存储到计算机存储器中，并为这些数据定义一个运算集合，就称为一个数据结构。

数据结构包含下面三方面的内容：

1. 数据的逻辑结构：表示数据运算之间的抽象关系（如邻接关系、从属关系等），按每个元素可能具有的直接前趋数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。
2. 数据的存储结构：逻辑结构在计算机中的具体实现方法，分为顺序存储方法、链接存储方法、索引存储方法、散列存储方法。
3. 对数据结构施加的运算：对数据进行的操作，如插入、删除、查找、排序等 。
   

• 数据类型可分为：非结构的原子类型和结构类型。
  • 原子类型的值是不可分解的
  • 结构类型的值是由若干成分按某种结构组成的。

数据类型在高级语言中指数据的取值范围及其上可进行的操作的总称

C语言中，提供 int, char,float,double 等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用 typedef 自己定义数据类型

typedef   struct  
{      int   num;char  name[20];float score;
}STUDENT;
STUDENT    stu1,stu2, *p;

抽象数据类型：

是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。

也就是说抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。

抽象数据类型的定义：

抽象数据类型名
{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉
} 抽象数据类型名

数据对象和数据关系的定义用伪码描述：
数据基本操作的定义格式：

基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉

抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

算法

算法（Algorithm）是一个有穷规则（或语句、指令）的有序集合。 它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。

举一个例子，常规简单数学题：求两正整数m、n的最大公因子。 算法如下：

	① 输入m,n； 	 ② m/n（整除），余数→r (0≤r≤n)；③ 若r=0,则当前n=结果，输出n,算法停止；否则，转④；④ n→m,r->n； 转②。

如初始输入 m=10,n=4,则m,n,r 在算法中的变化如下：

	m          n            r10         4            24          2            0(停止)  

即10和4 的最大公因子为2。

算法特性

(1)    有穷性 —— 算法执行的步骤（或规则）是有限的；
(2)    确定性 —— 每个计算步骤无二义性；
(3)    可行性 —— 每个计算步骤能够在有限的时间内完成；
(4)    输入 —— 算法有一个或多个外部输入；
(5)    输出 —— 算法有一个或多个输出。

这里要说明的是，算法与程序既有联系又有区别。二者都是为完成某个任务，或解决某个问题而编制的规则（或语句）的有序集合，这是它们的共同点。区别在于：其一，算法与计算机无关，但程序依赖于具体的计算机语言。其二，算法必须是有穷尽的，但程序可能是无穷尽的。其三，算法可忽略一些语法细节问题，重点放在解决问题的思路上，但程序必须严格遵循相应语言工具的语法。算法转换成程序后才能在计算机上运行。另外，在设计算法时，一定要考虑它的确定性，即算法的每个步骤都是无二义性的（即一条规则不能有两种以上的解释）

解决一个问题可以有多种不同的算法，在算法正确的前提下，评价算法好坏的方法 ：

消耗时间的多少 ：
消耗存储空间的多少 ：
容易理解、容易编程和调试、容易维护。
时间复杂度的概念介绍 ：
问题的规模：输入数据量的大小，用n来表示。
算法的时间复杂度 ：算法消耗时间，它是问题规模的函数 T(n)。

将上述 求两正整数m、n的最大公因子。 算法思路转换成C语言程序如下：

#include “stdio.h”
int main(void)
{ int m,n, j;  char flag=‘Y’;while (flag==‘y’||flag==’Y’){ printf(“\n”);scanf(“input= %d%d”,&m,&n);  //输入两个整数m,n//if (m>0 && n>0 ){ j=maxog(m,n) ;            //求m,n的最大公因子//printf (“output= %d\n”,j); } //输出结果//printf (“continue?(y/n)”);flag=getchar();              //输入’y’或’Y’继续，否则停止//}}int maxog(int m, int n)    //求m、n的最大公因子算法（或函数）//
{	 int r=m%n;while ( r!=0){ m=n;  n=r;  r=m%n; }return (n);  
}

前提：算法均以C语言的函数形式描述，而main() 和 数据 I/O 就不描述了。另外，由于某种原因（如参数错，存储分配失败等）导致算法无法继续执行下去时，约定调用函数 ERROR() 进行出错处理。

数据结构是研究从具体问题中抽象出来的数学模型如何在计算机存储器中表示出来；而算法研究的是对数据处理的步骤。如果对问题的数据表示和数据处理都做出了具体的设计，就相当于完成了相应的程序。编写代码执行层只是最后一步实现步骤。

算法分析初步

算法分析是指算法在正确的情况下，对其优劣的分析。一个好的算法通常是指：

1. 算法对应的程序所耗时间少；
2. 算法对应的程序所耗存储空间少；
3. 算法结构性好、易读、易移植和调试等等。

算法的时间效率

算法对应程序的时耗，有诸多因素，主要考虑程序中可执行语句的执行次数。为此，引入下面几个概念：

1. 语句的频度(Frequency Count)

语句频度定义为可执行语句在算法（或程序）中重复执行的次数。若某语句执行一次的时间为t，执行次数为f，则该语句所耗时间的估计为 t*f。

2. 算法的时间复杂度(Time Complexity)

算法的时间复杂度定义为算法中可执行语句的频度之和，记为T(n)。T(n)是算法所需时间的一种估计，其中n为问题的规模（或大小、体积）。如上图中，问题的规模n为矩阵的阶，该算法的时间复杂度为：

T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

当n->∞时，lim(T(n)/n3)=2，故T(n)与n3为同阶无穷大，或说T(n)与n3成正比、T(n)的量级为n3，记为：T(n) = O (n3) 。

例2：在数组中查找

在数组（A[1],A[2], …, A[n]）中查找最后一个与给定值k相等的元素的序号的算法

 int search(datatype A[n+1], datatype k) 
{    int i=n; A[0]=k;while (i>0 && A[i]!=k)  i--;return(i);
}

本例应以平均查找次数为算法的T(n)。设查找每个元素的概率pi(1≤i≤n)均等，即pi=1/n，查找元素k时，k与A[i] 的比较次数（即执行while循环语句的次数）Ci=n-(i+1)，,则查找次数的平均值（或期望值）：
因此，
故T(n)=O(n)，此时又称T(n)为算法的渐进时间复杂度。

算法效率的度量

• 算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量。（算法时间是由控制结构和原操作的决定的）
• 记号——引用了 “O”。“O” 表示一个 数量级的概念。
  根据算法中语句执行的最大次数（频度）来 估算一个算法执行时间的数量级。
• 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），

T（n）=O（f（n））

它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。

• 语句的频度：是该语句重复执行的次数。

T(n)的量级通常有：

O© —— 常数级，不论问题规模多大，T(n) 一致，因而是理想的T(n)量级；
O(n) —— 线性级；O(n2),O(n3) —— 平方、立方级；
O(log2n),O(n*log2n) —— 对数、线性对数级；
O(2n) —— 指数级，时间复杂度最差。

以上几种常见的T(n)随n变化 的增长率可以如图所示：

对较为复杂的算法，可分段分析其时间复杂度。如某算法可分为两部分，其时间复杂度分别为：

T1(n)=O(f(n)) , T2(n)=O(g(n))

此时两部分问题的体积一致，则总的 T(n)=T1(n)+T2(n)=O(max(f(n),g(n))
O(max(f(n),g(n)) 表示取 f(n)、g(n) 中最大者。

但若 T1(m)=O(f(m)) , T2(n)=O(g(n))，两部分的体积不一致，则：

T(m,n)= T1(m)+ T2(n)=O(f(m)+g(n))

另外，算法空间复杂度的定义：
设算法对应问题的体积（或规模）为n，执行算法所占存储空间的量级为D(n)，则D(n)为算法的空间复杂度(Space Complexity)。

#define n 100 
void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n])
{	int i,j,kfor (i=1;i<=n;++i)                      //n+1for (j=1;j<=n;++j)                   // n*(n+1){ C[i][j]=0;                      //n2for (k=1;k<=n,k++)    n2(n+1)C[i][j]=C[i][j]+a[i][k]*b[k][j];   //n3}
}

T(n)=n+1+n*(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

量级：T(n)=O(n3)

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！