数据结构解决了要处理的问题中信息的分析和存储，即把要处理的信息从实际的问题转换成了计算机能接收和理解的问题，接下来的工作就是对数据进行操作处理即数据的运算，以完成问题所要求的功能。数据的运算通过算法来描述。本系列的文章的前置要求是对一门高级语言比较熟悉，满足以下他条件可以被认为是熟悉:
- 函数的定义以及使用
- 基本语法，像判断、循环等
- 对于高级语言的一些特性要有一点了解(比如C语言的指针、结构体, Java的引用) 在我刚学数据结构的时候，因为我只会C，还不是很熟练，所以学数据结构的时候，只找C，但到现在其实我觉得思想是共通的，不要拘泥于哪种编程语言。所以本系列的文章在编写的时候，参考的书籍是用C语言来表示算法的，但是我将它转成了Java。如果你只会C语言，那么这里建议再学习一下其他高级语言，以便不会产生阅读障碍。事实上对于我这个Java程序员来说，Java也蛮清晰的，我在用Java表示算法的时候尽量不会使用Java独有的，尽量做到通用。
什么是算法?
做任何事情都要有一定的步骤，这些步骤是有顺序的，广义的说，算法就是为解决问题而采取的步骤和方法。在这个角度，我们可以将做菜特当做一种算法，为了吃到美食，我们按照一定的步骤和方法，做出美食。在程序设计中，算法就是计算机解决问题的过程，要求对解题方案有准确而又完整的描述。
具体地说，算法就是在有限步骤内求解某一问题所使用的一组定义明确的操作序列，能够在有限时间内，对一定规范的输入获得所要求的输出。
根据上面的话，我们可以得出算法的特征:
- 有穷性(在有限时间内): 一个算法必须保证在执行有限步骤后结束，而不是无限的。
- 确定性(定义明确的操作序列): 算法中每一条指定必须有明确的含义，而不能含糊不清有歧义。
- 可行性: 每一个操作步骤必须在有限的时间内完成。
- 输入: 一个算法可以有多个输入，也可以没有输入
- 输出: 一个算法可以有一个或多个输出，没有输出的算法是没有实际意义的。
##算法设计的一般步骤 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法。算法是问题求解过程的精确描述，不同的问题有不同的解决方法，一个问题也可能有多种算法可供选择。虽然前人已经设计出了很多经典的算法可以去借鉴，如迭代法、穷举搜索法、递推法、贪心法、回溯法、动态规范等(这些词看不懂没关系，我在刚学算法分析的时候也看不大懂，后面会结合案例来讲)。但算法设计依然是一件非常苦难的工作，其困难在于算法设计不同于一般的数学、物理问题，在明确问题后，有现成的公式可以套用。从算法是处理数据的步骤这个角度来看，我们可以大致给出算法设计的一般步骤:
- 设定算法的初始条件(做个类比就是，我要做猪肉炖粉条这道菜，至少一开始我要猪肉和粉条)
- 确定算法的结束条件(这道菜做到啥时候结束)
- 按问题的普遍规律，给出算法的处理流程(简单的理解就是，在做猪肉炖粉条的时候，脑子想想应该放什么料，先泡粉条。之后也按照这个流程来)
- 考虑异常情况.( 猪肉炖粉条一不小心酱油放多了咋整)
上面用了做猪肉炖粉条来举例，但是还不大形象，我们以求阶乘来再解释一下:
我们可以将算法的初始条件理解为算法从哪一个条件开始，比如求阶乘的算法就是从1开始，到达输入的n结束。阶乘的公式为: n!=1×2×3×...×n,这是问题的普遍规律，算法的处理流程为从1开始，做一个for循环，设定一个变量来存储每一次累加的值。异常情况就是输入的n为负数，我们直接返回-1.
如何评价算法的优劣
不同的做菜步骤做出来的菜会有略微的差异，我们以味道来评判这些菜是否好吃。那么对于算法来说，将算法限制在程序设计领域内，我们该如何评价算法的优劣呢？靠运行时间？短的胜出？那不同的电脑配置不一样，我们无法要求所有的电脑配置都是一样的，我们想给出的是一种通用的评价方案，不会受制于具体的电脑硬件。
我们来思考一个问题，若不考虑软硬件的相关因素，剩下的就只有算法的策略和问题的规模两项。这让我想起了函数的导数，导数可以用来衡量函数的增长速度，线性增长是平稳的，指数级增长是恐怖的。我们不仅要看在小规模下算法所需的时间，通常也要看随着问题规模的增大，算法所处理时间的增长幅度。
那么如何将算法时间效率的分析独立于软硬件系统呢? 一个算法所耗费的时间，应该是该算法各条语句执行时间之和，因此一个算法花费的时间应该与算法中语句的执行次数成正比。语句执行一次所需的时间取决于机器指令执行速度和编译所产生的代码质量，这很难确定。我们可以假定，每条语句执行一次的时间都是相同的，为单位时。在这样的设定条件之下，可以把算法的执行时间简单地用基本操作的执行次数(频度)来代替了。
如何计算算法对应语句的执行频度
for(int i = 1 ; i <= n ; i++){ // 执行的次数为n + 1 控制循环体的语句中的语句执行n次，i大于n的时候，因为还要执行一次比较所以这里是n + 1 ， 下面同理 for (int j = 1; j <= n ; j++) { // 执行的次数为n(n+1) c[i][j] = 0; // 执行的次数为 n的平方 for (int k = 1 ; k <= n; k++) { // n的平方 * (n + 1) c[i][j] += a[i][k] * b[k][j] // 执行次数为n的立方 } } }
各语句的执行频度之和为f(n) = 粗略的说，我们可以将这个函数称之为上面给的示例的算法复杂度，这个函数描述了随着n的变大，代码执行的次数增长幅度。但是这个函数有点复杂，我们希望更直观点，我们一般常用的是O(Big-O)(上界) ,( Big-Theta)(等限确界) , (下界)来表示算法的时间复杂度和空间复杂度，看到这个上界有没有想到高等数学中的上界和下界，有些概念是想通的，我们可以将fn简单的表示如下 < f(n) ≈ ( Big-Theta) < O(Big-O)。这也是一些算法教学视频中讲述算法的时间复杂度，说big O(n)的原因。大O符号(Big O notation)是用于描述函数渐进行为的数学符号，它是用另一个更简单的函数来描述一个函数数量级的渐进上界。在计算机科学中，它在分析算法的复杂性的方面非常有用。大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》中首先引入的。
它的数学意义如下: f(n) = O(g(n)) 若存在两个正常数c和n0 ，使得当n 大于等于n0时, 使得f(n) 小于或等于c * g(n),我们也一般称之为算法的时间复杂度。拿f(n) = 来说，它的算法渐进上限就是O()。
我们用定义去求时间复杂度有些时候有些不方便，这里我们再给出一种用极限的方式来求时间复杂度的方法。设f(n) 、g(n) 是同一个自变量n的变化过程中的无穷大，则二者的比率极限为:
当结果为1的时候，这个就是我们常说的等价无穷大，而结果如果大于等于0或者小于等于1，那么我们就可以说f(n) = O(g(n)) 也可以说n在增大的时候，g(n)比f(n)跑的快。
时间复杂度并不表示一个程序解决问题需要花多少时间，而表示当问题规模扩大后程序运行需要的时间长度增长得有多快。对于高速处理数据的计算机而言，处理某个特定的数据效率并不能衡量一个算法的好坏，而应该看这个数据的规模变大到数百倍后，程序的运行时间是否还是一样，或者也跟着满了数百倍，或者慢了数万倍。
常见的时间复杂度，按数量级递增排列依次为:
常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 多项式阶 < 指数阶
如果一个程序的算法具有对数级的基本操作次数，该程序对于任何实际规模的输入都会在瞬间完成；一个需要指数级操作次数的算法只能用来解决规模非常小的问题。通常认为具有指数阶量级的算法是实际不可计算的，而量级低于平方阶的算法是十分高效的。
当n取值很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此只要能将现有的指数时间的经典算法中的 任何一个算法转化为多项式算法，就可以说是一个很了不起的突破。
时间复杂度计算准则
设程序段1和程序段2的时间分别为T1(n)和T2(n),总的运行时间为T(n)。
- 加法准则
对于两个连续执行部分组成的算法，其整体效率是由具有较大的增长次数部分所决定的，即由效率比较差的部分决定。T(n) = T1(n) + T2(n) = O(f1(n)) + O(f2(n)) = O(max(f1(n), f2(n)))
- 乘法准则(程序嵌套)
对于循环结构，循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间范围，则可用大O下的"乘法准则"。T(n) = T1(n) * T2(n) = O(f1(n)) * O(f2(n)) = O(f1(n) * f2(n))
上面两个准则给我们的启示是，对于比较复杂的算法，可以将其拆分为几个容易估算的部分，然后利用加法法则和乘法法则来求出整个算法的时间复杂度。
算法的空间复杂度
算法的空间效率分析，与算法的时间效率分析类似，是要找到问题规模对算法运行所需空间的影响。具体的说，就是去除无关的因素之后，找到它们之间的对应函数关系。
一个算法所需的存储空间包含两个方面: 存储算法本身所需的存储空间，算法运行过程中需要的存储空间。算法本身所占用的存储空间与算法实现代码的长短相关，况且不同语言对不同数据类型分配的空间也是不同的，很难确定其余问题规模的函数关系。而一个算法确定了，其存储空间的大小也不会随着问题的规模的变化而发生改变，因此我们忽略掉这一部分的内存占用。
算法在运行过程中局部变量临时占用的存储空间会随算法的不同而异，有的算法z还需要占用少量的工作单元，而且不随问题规模的大小而改变；有的算法㤇需要占用的临时工作单元与问题规模n有关，它随着n的增大而增大，当n比较大的时，将占用比较多的存储单元。
我们下面来看一个典型的例子，来说明算法的空间复杂度该如何分析, 计算多项式的值f(x) = . 我们这里来给出对应的算法实现，
public float evaluate(float coef[] , float x , int n){ float f = 0.0f ; // 存放x的幂 float [] array = new float[n]; array[0] = 1; for (int i = 1; i < n ; i++) { array[i] = x * array[i - 1]; } for (int i = 0 ; i < n ; i++){ f = f+ coef[i] * array[i]; } return f; }
这道题目的规模n是多项式的系数。coef属于输出，局部变量中占比最大的是array，随着n的增大而增大。其他局部变量是x,f,i是与n增长基本无关的变量。所以按照时间复杂度的分析方法，该算法的空间复杂度为O(n)。有同学看到这里可能会问，x输入的很大的时候，会增加占用空间吗？每个基本变量在使用的时候分配的内存空间是固定的，不会随着变量的增大，占用内存空间变大。
空间复杂度是对一个算法运行过程中临时占用存储空间大小的量度，它也是问题规模n的函数，记做S(n) = O(g(n))。其中g(n)--执行算法所需的临时空间(也称为辅助空间)。
空间复杂度数学上的计算方法与时间复杂度一样，只不过空间复杂度是追求辅助单元总和的同阶上限，而时间复杂度则是求语句频度和的同阶上限。通常，一个算法的复杂度是算法的时间复杂度和空间复杂度的总称，我们使用"时间复杂度"表示运行时间需求，使用"空间复杂度"来表示空间需求。当不用限定词的使用"复杂度"时，一般都是指时间复杂度。
