转自本人的csdn博客
本人学习软开方面的算法只有一个多月，对很多问题的理解不是很深入，这里只是写出自己的想法，抛砖引玉，欢迎交流。

写在前面

在学习了这么多的视觉算法控制算法和编程算法之后，对整个算法体系有了一些感想，在这里记录一下。

算法是什么

很多人学习了很多算法，却根本不知道算法的本质是什么？但是深入说起来，这其实是一个哲学问题。
有些书说算法是帮主我们解决问题的方法。但是问题是怎么来的呢？没错，问题也是人提出来的，用人设计的算法去解决人提出来的问题，就意味着一个前提条件，即问题所在的空间内要包含问题的解。
接下来是传统算法和编程算法的区别，首先我把视觉统计控制什么之类的算法都归为传统算法，他们与编程算法最本质的区别就是，他们的解域都是无穷大的，编程算法是一定可以把所有可能结果都列出来的。
比如，我们要找int 1-10内最大的数，可能的结果只有1,2，3,4，5,6，7,8，9,10，那么直接挨个作比较就可以找到是10最大。
而现实中，我们要找1-10内最大的数，就没办法找到了，9.9是最大的吗？9.99比它还大，一直找下去可以找到9.99999...有人说直接取10不就是最大的，但我们怎么知道比10大的数不存在呢？在这里因为限制条件很简单，所以我们知道10在限制条件中是最大的输出了，但如果很复杂呢？我们只能通过求出精确解（解析解或数值解）来得到最大值，而不是把所有可能结果都遍历出来，挨个比较得到最大值。在数学上，一般求解这类问题用最优化，列一个方程f（x）=x，1<=x<=10。求导，在限制条件内找最大值，又由于方程是线性的，可以直接用线性规划。
所以，所有的编程算法本质上都是暴力求解（遍历），包括所有的排序，查找（其实排序和查找本质上是一样的），动态规划，剪枝，尺规，回溯等等等等都是基于暴力求解。注意这里蒙特卡洛，贪心算法，信息熵增益等算法并不属于编程算法，如果已经看懂了的朋友应该自然就能理解。
既然都是暴力求解，那提出这么多编程算法到底是为了干啥？
因为暴力求解时间复杂度太高，往往成指数增长，计算机性能开耗不起。而算法就是通过某种方法，来减少暴力求解的次数。
凭什么能减少？
从信息的角度来说，一坨数据包含的信息是非常丰富的，但对某个问题来说，并不是所有的信息都有用，如果我们能够剔除掉这些无用信息，只保留有用的，那么获取信息的成本就会大大减少。如果我们把一个问题分为无数个子问题来看的话，那么子问题也剔除无用信息在某些情景下会表现为不重复利用已有信息。
从逻辑的角度来说，对当前问题来说，很多工作被重复进行了。
实际举例：
a，b，c三个数排序，已知a<b，之后又计算出了b<c，那么还需要计算a<c吗？
对排序问题来说，在知道a<b和b<c之后，a和c的关系就已知了，再进行比较是无意义且重复的。
减少次数的代价是什么？（以下为个人民科，不看也罢）
我们知道物质和能量是可互换的，不能凭空减少也不能凭空增多。
在信息领域也是如此，信息在时间上的量和在空间上的量总数是一定的，只能从时间量转换为空间量，或从空间量转换为时间量。
也就是说我们算法节省出来的时间，必然要花费一定的空间来弥补回来，不可能存在时间和空间双赢的算法。但是这种换算并不一定是线性的，而且存在某个换算是对计算机系统最友好的（对别的系统可能就不一定了）。
举个例子：
已知a<b，b<c，在进行a和c时可以直接跳过，那么在进行a和c的比较时，我们怎么知道要直接跳过了。假设这是一颗树状结构，b在根节点，c插入的时候，插在了b的右侧，再来插入a的时候，a已经进入了b的左分支，永远不会再与c相见，自然不需要继续比较。所以在这里就是通过树的结构来耗费空间从而节省时间。
基本所有排序和查找都是利用空间换时间。
哈希除外，哈希本质上操作次数并没有减少，但是哈希把寻址操作直接丢给了内存空间寻址，硬件操作当然比软件操作快的多了。
而剪枝算法其实也是通过空间换时间，只不过它的空间只利用了一次。（剪枝其实就是瞬时的树）
动态规划其实也是空间换时间，但是动态规划并不保证算法有效，它只是假设了大多数信息内容都差不多，并以此为出发点构建状态转移矩阵。
假设当前背包容量为10000，而只有三个物体，分别重9990,9，1，这时候再用动态规划，状态矩阵直接爆炸。

增补：其实很多传统算法也是通过暴力迭代的方式去求解的，但是在每一次迭代内部使用了启发性的算法，而不是像软开算法一样，在暴力迭代的内部使用if判断。

线性问题（个人民科）

在传统领域，例如控制系统，是极力避免出现非线性系统的，出现了也要在某个区间上近似为线性系统。在数学上，非线性的函数问题也比线性函数的问题复杂得多。在物理上，传统物理都是线性的，直到微观领域中，线性条件不成立，所以人们引入了量子力学，波函数等等东西，才有了一些列怪异又烧脑的物理学理论。
首先讨论问什么现实世界中线性系统的亲和度那么高呢？换句话说为什么现实世界中的线性系统对人类更友善？
首先是数学上的，一直到大学时我们所学的大多数数学方法和公理都是基于线性空间的，非线性的理论一般只存在于大佬的脑海中。所以对大多数普通人来说线性系统更容易理解和掌握。并且我个人认为人类的整套数学体系都是建立在线性模型上的，从最基础的数字组合到加减法乘除法再到函数，都是线性的。而一些非线性理论，其实也是在尝试用线性的观点去解释非线性的现象。
其次是人类逻辑上的，我个人认为人类的思维方式也是建立在线性模型上的，因为从古至今人类观察到的所有信息（声光触觉嗅觉都是连续的电信号），可以控制的所有运动（电信号->机械运动，各种肌肉）都是线性的，人类的思维很自然就进化成了基于线性系统的思维。
说了这么多，有什么用呢？
我个人认为计算机系统中出现的很多问题属于非线性问题，而算法或工具框架的作用就是把这些非线性问题转换为线性问题。其实大多数问题并不是真正意义上的非线性，而是宏观展现出来是非线性的。
比如计算机的并发问题，两个线程同时让变量a+1，很可能线程A取出来a然后+1，线程B取出来a然后+1，但最后只加了1。而一个线性系统，比如给杯子倒水，线程A倒1毫升水进去，线程B也倒1毫升水进去，无论它们什么时候倒，都会倒进去2毫升。
那么并发问题的非线性发生在什么地方呢？寄存器内。
在其他时刻，比如变量还处于内存中时，它永远是线性的。但是一旦取出到了寄存器内时，寄存器无法跟外部同时共享信息，它这时候就变成了一个时间暂停的状态，如果画成函数的话，它在这个点是一个断点，也就是变成了非线性状态。同样的从寄存器向内存写入的时候，又是一个断点。这是造成非线性的两个地方。
通过锁等方式，使内存和寄存器看起来共通了，两个状态变得完全一致，也就不存在断点了。
下面说说算法。在这里先要自创一个概念，算法在迭代的过程中，有序度的变化，有序度可以用信息熵等描述，在迭代结束后，肯定各个算法的有序度都是一样的，但是在迭代过程中，有的算法有序度可能是线性增长的，有的算法有序度可能是指数上涨的。算法有序度的增长越线性，那么这个算法可能就越好（猜的）（可以分别以时间或空间度量为横轴）。
首先，暴力算法肯定是所有问题的通解，比如暴力排序，看起来暴力排序每次排好一个数，很像是线性但，但是暴力排序遍历的次数太多了，实际上它的有序度是一个阶梯增长的，这个东西线性度是非常差的。而快速排序和归并排序，看起来就就很优美了，归并排序比较好计算，很显然它也是一个阶梯函数，但是每个阶梯内是指数增长曲线，所以线性度比暴力排序高的多。
而对快速排序来说，这个阶梯又变成了高度不统一的，且阶梯内的增长曲线参数也不统一，而且在接近零点的最初阶段是非常近似线性的（没有计算过，仅凭感觉）。

仿真与模拟

这两个往细了说是由区别的。
仿真是已知系统的运行规则，把系统的状态作为输入，就可以得出一个输出，这个输出应该是严格准确的。
模拟是已知或未知系统的运行规则，构建一个新的系统模型，使新系统的输出尽可能接近原系统的输出，也可以叫拟合（不过这是我自己的定义，实际上可能不是这样）。
首先用电路来解释一下仿真和模拟，假如我有一个电源，一个电阻，一个并联电路每个支路连接了一个灯泡。
那么仿真就是模拟每一个电子在电路中的运动，或者计算每一个电路节点的电压变化，用这种方式来得出每个支路电路上的灯泡是否会亮。
而模拟就是，我们高中都学过并联电路的计算公式，直接代入公式进行计算，即可得出结果。
计算机系统中常用的都是仿真，包括我们做电商做数据库做游戏都是仿真。首先以游戏系统为例，这个比较容易讲清楚。
假设游戏中我们有10个工人采矿，在游戏引擎中，每个工人有自己的运动方式，会在与游戏场景（地图）不断交互（运动，挖矿，运输矿），这里面的每一个步骤都是一次仿真，随着游戏的逻辑帧不断更新，每个工人或者说游戏世界中的每个对象都在运行得井井有条。我们可以在任意时间查看某个工人的坐标，看他的速率，看他是否正在采矿，看他是否正在运输矿物。
如果我们现在统计已储存的矿物数量，可能会得到一个列表[0,0，0，0，0，10，10，20，30，30，40，40，50，50，50，50，60，60，70，70，80，80,...].
假如游戏中有10000个矿工呢？那我们的游戏引擎每一次逻辑帧中都需要计算10000次运算，这个开销太大了。而实际上，我么此时可能不需要知道每个矿工在每个具体的时刻到底在哪个位置，我们可能只需要知道总的矿物储量如何变化即可。
这是就可以构建一个模型，比如f(t)=F(t);此处可以用数学模型推导，例如f(t)=xkt（x个工人，系数k）；也可以用使用统计学方法，例如f(t)= F^ (t) s.t. min (F^(t)-F(t)) ^ 2，也就是说我们先用仿真法统计出100个工人在一段时间内采矿的情况，建立模型，然后再扩展为100个100工人模型进行汇总；
这时需要考虑一个问题，就是我们在模拟时一定是丢失了一些信息，模拟的系统绝对不可能达到100%的近似原仿真系统。就比如说我们现在某个矿场采空了，使用模拟方式的话，不会立刻知道该矿场采空了，需要过一段时间才能感知到，这里就会有一定的误差，所以我们才只在10000人的情况下使用模拟，因为此时误差可以忽略不计（当然电商的时候不可忽略这种误差，不过游戏系统可以）。
还有一个问题，仿真和模拟需要实时切换，就如之前所说，只能在特定条件下使用模拟（长期稳定、允许误差、只关注一部分数据），而游戏世界是在不断变化的，比如某时刻一部分旷工突然因为幸福度下降而罢工，那么就需要立刻将这部分的模拟关停，而使用仿真（仿真初始输入还需要另行计算）。
另外例如单人3A开放世界大作，核心关注动作或剧情或小规模战斗的时候，可以用模拟方式更新主角远距离的世界信息，而使用仿真的方式更新主角近距离的世界信息。
另外模拟还可以不在每一逻辑帧中都进行更新，而只是在需要用的时候更新（不过这样做的前提是，间隔不能太久，而且需要在每次操作时都打上时间戳）。
接下来说一下电商或者数据库的仿真，电商中比如，用户买了一个商品，我们把这个过程真实发生了，顾客扣钱，商品所有权转移到了顾客身上。假如该顾客每过一分钟都下一次单，那么都要进行一遍这种操作。
现在有一个大胆的电商黑天鹅，采用了未来预知技术，它预测顾客今天会买一百个这种商品，所以直接进行一次扣除100*单价的费用，然后获取100个商品给顾客，这就是模拟。
很显然在电商中用模拟是要进局子的。
在数据库中其实可以小部分的用一下，不过由于我目前还没有学习数据库，所以暂时空着。

改进

字符串匹配

我尝试了暴力匹配和KMP匹配，KMP本质就是利用了已经匹配的部分信息，然而使用KMP是有条件的。
所以我加上了剪枝算法，即相同的字符串，那么它们的和也一样，按数值进行各种计算的值也应该是相同点，或者统计学属性也是相同的。
先把不同的剔除掉，再在剩下的部分中进行计算。（貌似某种哈希字符串匹配算法就是这么干的）
但是后来发现其实性能开销更大，需要专有底层计算组件的支持才能使效率更高。
前几日阿里的面试官问我有没有大O为n的字符串匹配算法，我想了一下貌似都是mn的，然后没答出来，之后思考了字符串匹配的问题，为什么会出现mn？是因为匹配串中有重复的信息出现，那么如何减少这一重复信息呢？
考虑到连续两次出现重复信息的概率是2626（仅限英文不区分大小写），而对Unicode来说，连续两次出现的概率是6553565535，这个值实际上已经不需要考虑重复问题了，然而现实中却经常出现了重复问题，实际上是由于65535的编码中常用的并不多，就以英文为例，用的最多，却只占了26个位置，而且有大量相似词根，所以很容易出现重复。
考虑到无论字符占多大位置，每次判断，cpu都是变量a-变量b是否等于0来算的，而变量a和b的大小可以是cpu的运算大小，一般是32的，而我们的英文字符串26只占了5位，浪费了太多的算力。
所以字符串匹配时可以合并，比如将abc按照字典序重新编码，然后3个一组3个一组进行匹配，不断滑动窗口，如果相等再转入更精细的单个匹配。
这样实际上也至少需要n次匹配，然而基本不用考虑mn的情况了，因为出现一次重复的概率为2^64，约等于10e82 而地球上可用的原子估计也不会超过这个数。

一维匹配

即字符串匹配，数组匹配等。很显然，程序员的思维是直接暴力挨个匹配，而我所在的老本行就会采用卷积（卷积本来就是做相关函数判断的），不过要进行归一化处理，并且需要扩展待匹配字符串的长度，但是由于匹配出的是相似度而不是匹配度，所以不太适合用于字符串匹配，而适合用于数组匹配（如果通过某种方式将字符串正则化之后，也许可以实现语义匹配，不过这可能就是NLP的某些算法提供的功能了）。

线程池控制

线程池本质上是用来控制线程的数量，我们考虑如果不设置线程池，来一个任务开一个线程，那么假如某个瞬间来了一坨任务，就会有一个冲击值，这时候如果不控制线程数量，将会很可怕。但现在的线程控制都太硬了，程序会精准的控制线程到某一个值，不会超出也不会减少。
而考虑到我本科专业所学的自动控制原理，现实基本任何控制系统都会有响应时间的，所以我没有使用硬性控制，而是大致上控制，并不断检测控制差值，来实现一个平稳过度，仅使用原子量而不使用锁。

多线程加速排序

考虑到所有排序算法中只有归并排序和希尔排序是可以多线程的，于是先将整个集合分为三段，每段都用线程进行快速排序，然后再对三段进行三三归并。（如果分为四段的话，可以两两归并）。
即归并排序的第一轮不是2个长度，而是任意长度，然后对这个任意长度采用多线程并行的快速排序，之后再进行单线程的归并排序。

哈希冲突概率

哈希算法最关键在于哈希函数，哈希函数需要保证一一映射，没有冲突，即要求函数的周期长（最完美的周期性长的函数线性函数），而使用傅里叶变换可以大致看出一个函数的周期性，高频分量越高，周期性越差，低频分量越高，周期性越强。

贪心动态规划

之前提到了，假如背包的容量很大，使用动态规划的开销也很大。可以将大背包分成许多个小背包，然后对每个小背包求得最大价值，最后再将结果合成。只不过这种算法求得结果是分步贪心的，结果不一定是最优解，甚至都不一定是局部最优解。

动态规划

学习动态规划两三天了，刷了大概四五道题目，发现了动态规划的意义所在。首先，动态规划的空间开销是很大的，它需要一个巨大的状态转移矩阵来存储我们的状态值，那它是如何节约时间开销的呢？
它通过简易的更新方式来节约开销，因为大多数动态规划在更新的时候，只需要比较1次或2次等很少的次数。假如我们把暴力算法写成状态矩阵的话，那么每次更新就需要遍历上一次状态表的全部维度，那么这个开销是很大的。而能使用动态规划解题的题目都是可以在有限步推导内求出新的状态转移矩阵元素目标值。
思考为什么那么多题目都可以用动态规划去解题？因为按照哲学原理来说，世界上的问题的最优解应该是随机而平衡的。其实并不是动态规划更适合解题，而是人类的思维更适合动态规划，有些题目实际上是有更合适的求解算法的，然而大多数人想不到，人们只能想明白动态规划。因为人的大脑结构就跟动态规划很相似。
那么在实际问题中，如何判断该算法题是否可以用动态规划，或者说是否使用了动态规划会更有效（所有问题都可以使用动态规划，只不过有些用了还不如直接暴力）？
比较官方的解释是，可以把问题划分为很多的子问题，然后可以通过求解子问题来求解整个问题。这句话的前半句话是废话，因为任何问题都可以划分为无数的子问题，而关键在于是否可以通过求解子问题来解决完整问题（其实更准确的说是是否能够通过求解简单的子问题从而解决问题）。目前我的理解是，如果一个问题解决它需要计算完整而又庞大的信息，但是划分为子问题后，解决子问题只需要一部分少量的信息，即求解子问题的难度跟子问题和完整问题的规模呈下降关系，如果下降不是很多的话，也没必要使用动态规划了。
笔试的时候如果一道题目没有其他合适方法的话，就直接上动态规划。
而复杂状态更新方式的动态规划，我们称它为神经网络。