算法与数据结构
概念数据：数据是能被计算机识别、存储和加工处理的具有一定结构的符号的总称
数据项：具有独立意义的不可分割的最小的数据单位。
数据元素：是数据被使用时的基本单位，在计算机程序中通常作为一个整体进行处理。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据结构：由一个数据元素的集合和一系列的基本运算组成。
数据结构包含：逻辑结构、存储结构
逻辑结构：数据元素之间的关系成为数据的逻辑关系，它与数据的存储无关（数据的逻辑结构是从逻辑关系上描述数据），是独立于计算机的。
线性结构（一对一）
实例：学生成绩表、个人身份证信息等。
树状结构（一对多）
实例：公司部门所属表、中国地区分布图等。
图状结构（多对多）
实例：课程教学安排、工作分配表等。
存储结构：数据结构在计算机中的表示称为数据的存储结构，也称为物理结构。它包括元素的表示和关系的表示。
顺序存储结构:把逻辑上相邻的元素存储在一组连续的存储单元，其元素之间的逻辑关系由物理位置的相邻关系表示。
优点：节省存储空间（分配的存储单元全用于存放元素的数据）。
缺点：不便于修改（修改时需要移动一系列元素）。
链式存储结构：将每个数据元素单独存放，称为一个结点，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针段，用于存放下一节点的存储地址。
也就是说：南京的结点存放的是成都的地址，所以该结点指向的下一结点为成都，而北京结点的下一结是上海。
优点：便于修改（修改时仅需改结点的指针域，不必移动结点）。
缺点：存储空间的利用率低（分配的空间没有全部用于存放数据之间的逻辑关系）。
算法：对特定问题求解步骤的一种描述
一个算法应该具有的特性：
有穷性：一个算法必须总是在执行执行有穷步之后结束，且每一步都在有限时间内完成；
确定性：算法中的每一步必须有确切的含义，不存在二义性；
可行性：算法中的每一步都可以通过已经实现的基本运算执行有限次来实现；
输入：一个算法有0个或多个输入，这些收入取决于某个特定的数据对象集合；
输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
算法描述的三种方式：非形式化、半形式化、形式化
评价一个好算法的标准：
正确性：算法应满足具体问题的需求；
高效性：算法执行时间的长短，时间越短，效率越高；（算法的效率也称为时间复杂度）
低存储量需求：指执行期间所需的最大存储空间（算法的存储量又称算法的空间复杂度）。
算法分析：时间复杂度分析和空间复杂度分析
时间复杂度（算法的重复次数）：T（n）=O（f(n)），常见的有：常量阶O（1），线性阶O（n），平方阶O（n^2）、立方阶O(n^3)、对数阶、指数阶。
算法的时间复杂度
取决因素：实现语言、编译程序所产生目标代码的质量、硬件的速度、问题的规模。
问题的规模：和输入量有关的量，如元素的个数、矩阵的阶数等。
撇开与计算机硬件有关的因素，可以认为一个特定的算法“运行工作量”的大小只依赖于问题的规模n，它是问题规模的函数。
实例：两个n阶方阵相乘
voidmultiplyAB(inta[n],intb[n])
{
inti,j,k;
for(i=0;in;i++)
{
for(j=0;jn;j++)
{
c[j]=0;
for(k=0;kn;k++)
c[j]+=a[j]*b[j];
}
}
}
该算法中采用三层嵌套循环，算法的重复次数为n^3（问题规模），其时间复杂为T(n)=O(n^3)。
算法的空间复杂度：是执行算法过程中所使用的额外存储空间的开销。不包含算法程序代码和所处理的数据数据本身所占用的空间部分。通常情况下，额外空间与问题的规模有关。记为：
S（n）=O（f（n））
n为问题的规模。
若额外空间相对于输入数据量是常数，则称此算法为原地工作。