算法的本质

算法的本质就是数学。

为什么要学习算法

由于工程中使用到的语言基本封装了像排序、数学运算等基本的工程必备的算法操作，再加上工程中的代码大都是一系列基本的逻辑，所以大多程序员的感知来讲，基本用不到算法。学习算法的意义在于了解算法背后的思想，这些思想可以在不经意间运用到工程当中，在一定程度上可以反映出程序员的内功，更能写出高质量、高效率的代码。

计算机中的一维坐标系和二维坐标系

一维坐标系定义：

选某一坐标为坐标原点，以某个方向为正方向，选择适当的标度建立一个坐标轴，就构成了一维坐标系，适用于物体在一维。

二维坐标系定义:

数学定义的二维坐标系：右方向为x轴，向上为y轴。

计算机中的二维坐标系：数学定义的二维坐标系顺时针旋转90度，即向下为x轴，向右为y轴。

例如: 距离x轴45度的经过原点的方程式为y = x，将该直线向右平移一位为y = x + 1，该直接的斜率为1，截距为1。

四方向向量和八方向向量

中间的坐标为（x，y），那么它上下左右四个方向的坐标为多少？

根据计算机的二维坐标向量，往上x轴减小，往下x轴增大，往右y轴增大，往左y轴减小；再加上方向向量的定义，那么上下左右的四个坐标分别为：：（x-1， y），（x+1，y），（x， y-1），（x，y+1）。

中间的坐标为（x，y），那么它左上、左下、右上、右下四个方向的坐标为多少？

同四方向坐标的推理过程，左上、左下、右上、右下这几个方向可以在x轴和y轴两个方向上进行拆分。例如，左上的可以看作y轴减1和x轴减1的组合。所以，这几个坐标分别为：：（x -1， y-1），（x+1，y-1），（x-1，y+1），（x+1，y+1）。

算法复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度时间是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）

时间复杂度的频度

一个语句的频度指的是该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T（n），它是算法问题规模n的函数，时间复杂度主要分析T（n）的数量级。算法中基本运算（最深层循环内的语句）与T（n）同数量级，因此通常采用算法中基本运算的频度来分析我们算法的时间复杂度，记为Big（O），T（n）= O（fn），简写为O（n）。

时间复杂度

在计算机科学当中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间，这是一个代表算法输入值的字符串的长度的函数，时间复杂度用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为渐进的，亦即考察输入值大小趋近于无穷的情况。

在T（n）= O（f（（n））这个式子当中，O的含义是T（n）的数量级，其严格的数学定义是：若T（n）和f（n）是定义在正整数集合上的两个函数，则存在正常数C和n0，使得当n ≥ n0时，都满足 0 ≤ T（n）≤ Cf（n）。

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质。

例如给定一个int类型的数组A[0... n-1]当中，查找给定值k的算法大致如下：

int i = n - 1while (i >=0 && (A[[i] != K))  i--;return i

该算法中第三行语句的频度不难发现实际上和n的规模有关，并且和A的各个元素的取值和k的取值都有关系。

如果A的所有元素中没有和K相等的元素，则第三行的代码的频度为f（n）= n

如果A的最后一个元素等于k，那么第三行的代码的频度为f(n) = 0

即所谓的最坏和最好的时间复杂度，通过最坏和最好时间复杂度的概念我们可以得到平均时间复杂度。

最坏时间复杂度：最坏时间复杂度指的是最坏情况下，算法的时间复杂度，也就是我们上述代码第三行的A的元素没有和k相等情况下的复杂度。

最好时间复杂度：最好时间复杂度指的是在最好的情况下，算法的时间复杂度，例如A的最后一个元素恰好等于k。

平均时间复杂度：平均时间复杂度指的是所有可能输入实例在等概率出现的情况下，算法期望的运行时间。

分析一段代码或者一个算法的时间复杂度的时候，有以下两条规则：

加法规则：T（n） = T1（n）+ T2（n）= O（f（n）+ O（g（n）））= O（max（f（n），g（n）））乘法规则：T（n）= T1(n) T2(n) = O(f(n) O(g(n))) = O(f(n) * g(n))