1.0 前言
 
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
 
简单地说，算法其实是解决问题的方法，他不是属于计算机方面的一个专属名词。不正式的说，算法是任何定义明确的计算过程，比如买菜大妈的买菜策略，骗子的坑人步骤，再比如高考中数学的立体几何，有的人写二十行，有的人写四十行，他们都写上了属于自己的算法，但是效率不同。
 
复杂一点的，再比如：一个环卫工人要清扫五个地点：
 
 
她也有不止一种执行完这个任务的方法：
 
 
 
那到底哪种方法走的路比较少？这就是我们之后要学习的最短路算法。
 
 
 
下面举一个例子来了解算法：
 
我们从小都见过的小学奥数题：有一口井七米深，一只青蛙从井底爬上来，白天爬了三米，晚上掉下两米，这样它要爬几天才能上来？
 
我们最笨的解题步骤
 
让青蛙爬三米
判断是否爬上去了
让青蛙掉下两米
重复上述过程并记录天数
（而不是计算得出一天爬一米，得出七天爬上来）
 
或者另一种算法：
 
最后一天直接爬上去：7-3=4米
其余天，一天一米：路程/速度=4天
4+1=5天
由此可见，我们首先要保证算法的正确性，其次要保证算法的效率，我们比较一下上述算法：
 
计算得出一天爬一米，得出七天爬上来，这种算法是错误的
模拟法，让青蛙模拟整个爬井的过程，我们看看有几次运算：
0+3=3，3<7
 
3-2=1
 
次数：0+1=1
 
             
 
1+3=4，4<7
 
4-2=2
 
次数：1+1=2
 
 
 
0+3=3，5<7
 
5-2=3
 
次数：2+1=3
 
 
 
0+3=3，6<7
 
6-2=4
 
次数：3+1=4
 
 
 
4+3=3，7=7，爬出来了
 
次数：4+1=5
 
一共进行了19次运算
 
公式法：7-3=4，3-2=1，4/1=4
进行了3次运算
 
 
 
从这个对比中应该能感受到算法不同，效率差距是很大的，然而感受其实的还不够。
 
试想：
 
假如这口井是100米？1000米？10000米？随着深度的增加，模拟法的计算次数也再增加，和深度成正比。
 
而再看公式法，其实和深度并没有什么关系，不管深度是多少，公式法永远只用计算3次即可。
 
这种计算次数和条件的大小，数量等因素没有关系的算法，视为非常优秀的一种算法。
 
 
 
       那我们计算机的算法到底是什么？我们提到，算法不是计算机领域才拥有的概念，它可以用任何方式来描述，我们之前接触到的基本都是用文字来表达，比如我在上文中列出的解题步骤。而我们要干的事，或者说计算机的算法要干的事，就是用代码来描述计算机上的处理过程。我们用一行行的语句来描述一个个解决问题的方法，这就是编程。
 
       计算机所有算法都是通过基本语句一点点描述出来的，比如上文的模拟算法：
 
让青蛙爬三米
判断是否爬上去了
让青蛙掉下两米
重复上述过程并记录天数
其中涉及到编程的很多基本语句：加减法、条件判断语句、循环语句等，编程语言也有很多，但是只是一个工具而已，就和汉语英语一样，并且单词数量比这两种语言少很多。所以只要脑海中的思路足够清晰，我们用一种（编程）语言把它描述出来即可，而不是我们之前去用汉语描述。
 
 
 
事实上，计算机的算法解决的问题可能是更加实际的问题，关系着我们每个人的生活，比如地图app如百度地图，高德地图，是如何帮你规划的路线的？再比如双十一如此疯狂的购物，各大购物网站是如何保证不会崩溃的？再比如到现在还没解决的问题：微博到现在为止，志玲姐姐结个婚，服务器都会崩。
 
如何衡量一个算法到底优不优秀？我们下篇来讲。
 
 
 
 
 
1.1何为算法
 
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
 
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
 
下面为算法的五个特性：
 
 
 
有穷性（Finiteness）
 
算法的有穷性是指算法必须能在执行有限个步骤之后终止；
 
 
 
确切性(Definiteness)
 
算法的每一步骤必须有确切的定义；
 
 
 
输入项(Input)
 
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
 
 
 
输出项(Output)
 
一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
 
 
 
可行性(Effectiveness)
 
算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
 
 
 
1.2衡量算法的指标
 
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
 
用几句话简单说明一下时间复杂度。
 
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
 
1）不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；
 
2）数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；
 
3）而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。
 
4）还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。
 
注意：不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。
 
因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
 
 
 
而空间复杂度是相似的，只是他的单位不是时间，而是空间，可以认为是内存。
 
 
 
2.1计算机
 
说完算法，我们来谈谈计算机吧。
 
计算机的优势非常明显：速度、记忆、精确，但是它也不是万能的。
 
就算计算机速度快，也不可以给他无限大的工作量，就算计算速度再快的计算机，在O(N^N)等复杂度的算法面前，也是无能为力，具体使用那种算法是人说了算，计算机无条件执行，这就对编程的人提出了要求。
 
       计算机的容量是非常大的，但是也不能存无限多的东西，同样的问题，解决方法不同，花费的空间差异也是巨大的。
 
       计算机是精确的，但是解决问题的方法和人类不一样，比如计算机很难回答某件物品“美不美”，“值不值”，再比如很多算法对人类是很直观的，可以用语言描述，但是转化成机器语言会花很多时间。
 
       总而言之，请善待你的计算机啦。
 
 

 
文章目录
 
贪心算法
一、前言
一、基本思路
1. 思想
2. 过程
(1) 算法实现过程
   
   
二、算法对比
三、经典问题
1. 股票收益最大问题
   
四、相关题目
 

 
贪心算法
 
一、前言
 
 
贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取 在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
 
 
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
 
 
一、基本思路
 
1. 思想
 
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度（贪心策略），每一步都要确保能获得 局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
 
2. 过程
 
建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解。
 
(1) 算法实现过程
 
从问题的某一初始解出发；
 while 能朝给定总目标前进一步 do，求出可行解的一个解元素；
 最后，由所有解元素组合成问题的一个可行解。
 

 
二、算法对比
 
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
 
 
贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
 
 
对于大部分的问题，贪心法通常都不能找出最佳解（不过也有例外），因为他们一般没有测试所有可能的解。贪心法容易过早做决定，因而没法达到最佳解。例如，所有对图着色问题。
 贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用。
 
 
三、经典问题
 
1. 股票收益最大问题
 
来自LeetCode：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 
 贪心策略：
 
单独交易日：
  后一天与前一天的收益：P2 - P1，可能为正，为负，为零。
连续上涨交易日：
   设开始涨买入价格为 P1,结束涨卖出价格为 Pn，(P1 < P2 < … < Pn)，则收益为 Pn - P1，也可表示为( (P2 - P1) + ( P3 - P2 ) + … + ( Pn - Pn-1 ) )
 
选择所有收益为正的。
 
package indi.pentiumcm.leetcode;

/**
 * @projName: algorithm
 * @packgeName: indi.pentiumcm.leetcode
 * @className: Q17
 * @author： pentiumCM
 * @email： 842679178@qq.com
 * @date: 2020/4/2 15:38
 * @describe: LeetCode-122. 买卖股票的最佳时机 II
 */
public class Q17 {


    /**
     * 贪心策略来实现
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int maxIncome = 0;

        for (int i = 0; i < prices.length - 1; i++) {
            int income = prices[i + 1] - prices[i] > 0 ? prices[i + 1] - prices[i] : 0;
            maxIncome += income;
        }

        return maxIncome;
    }


    public static void main(String[] args) {
        int[] arr = {7, 1, 5, 3, 6, 4, 5};
        int income = new Q17().maxProfit(arr);
    }
}
 
补充：
 对于可以使用贪心算法解决的问题，一般都可以使用动态规划来解决，因为两种都是基于最优子结构性质，但是如果贪心算法可以解决的问题，使用动态规划，就有点杀鸡用牛刀了。
 
这道题目动态规划的解法：
 
    /**
     * 动态规划来实现
     *
     * @param prices
     * @return
     */
    public int maxProfitV2(int[] prices) {
//      剪枝处理
        if (prices.length <= 1) {
            return 0;
        }
        if (prices.length == 2) {
            return prices[1] - prices[0] > 0 ? prices[1] - prices[0] : 0;
        }


//      1. 原问题划分为子问题
//         原问题：n天中股票最大收益
//         子问题：n-1中股票最大收益
//         子问题：n-2天中股票最大收益

        
//      2. 定义状态：dp[i] - 第 i 天的股票最大收益
        int[] dp = new int[prices.length + 1];

//      3. 定义初始状态  
        dp[0] = 0;
        dp[1] = 0;

//      4. 状态转移方程：dp[i] = dp[i-1] + 第i天当天的收益 
        for (int i = 2; i <= prices.length; i++) {
            int income = prices[i - 1] - prices[i - 2] > 0 ? prices[i - 1] - prices[i - 2] : 0;
            dp[i] = dp[i - 1] + income;
        }
        
        return dp[prices.length];
    }
 
四、相关题目
 
leetcode：
 

贪心算法
 
基本要素：
 
贪心选择：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
 
过程：
 
建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解。
 
（一）汽车加油问题
 
问题：
 
一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。
 
输入格式:
 第一行有 2 个正整数n和 k（k<=1000 )，表示汽车加满油后可行驶n公里，且旅途中有 k个加油站。 第二行有 k+1 个整数，表示第 k 个加油站与第k-1 个加油站之间的距离。 第 0 个加油站表示出发地，汽车已加满油。 第 k+1 个加油站表示目的地。
 
输出格式:
 输出最少加油次数。如果无法到达目的地，则输出“No Solution!”。
 
输入样例:
 7 7
 1 2 3 4 5 1 6 6
 
输出样例:
 4
 
贪心性质分析：
 找到汽车满油量时可以行驶的最大路程范围内的最后一个加油站，加油后则继续用此方法前进。需要检查每一小段路程是否超过汽车满油量时的最大支撑路程。
 
代码：
 
function greedy(n,k) {
        var count=0;
        var arr =[];
        //随机分配arr的每个数，即第i和i-1个加油站之间的距离
        for (var i =0 ;i <=k;i++){
            arr[i] = parseInt(Math.random()*10+1);
        }
        console.log(arr);//5 8 6 1 9 10 8 4 3 6 9

        var  num=0;
        for(var j=0;j<=k;j++)
        {
            count+=arr[j];
            if(count>n)
            {
                num++;
                count=arr[j];
            }
        }
        console.log('汽车最少要需要加油的次数为：'+num);//8
        return ;
    }
    console.log(greedy(10,10));
 
（二）背包问题
 
**部分背包问题：**固定容积的背包能放入物品的总最大价值
 
物品 A B C D
 价格 50 220 60 60
 尺寸 5 20 10 12
 比率 10 11 6 5
 
按比例降序尽可能多放入物品
 
function greedy(values, weights, capacity) {
    var returnValue = 0;
    var remianCapacity = capacity;
    var sortArray = [];
    values.map((cur, index) => {
        sortArray.push({
            'value': values[index],
            'weight': weights[index],
            'ratio': values[index]/weights[index]
        })
    })
    sortArray.sort(function(a, b) {
        return b.ratio > a.ratio
    })
    console.log(sortArray)
    sortArray.map((cur, index) => {
        var num = parseInt(remainCapcity/cur.weight)
        console.log(num)
        remainCapacity -= num*cur.weight
        returnValue += num*cur.value
    })
    return returnValue
}
 
（三）买卖股票的最佳时机
 
121. 买卖股票的最佳时机
 
只要记录前面的最小价格，将这个最小价格作为买入价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益。
 
var maxProfit = function(prices) {
    let maxP = 0;
    let minP = prices[0];
    for (let i = 0; i < prices.length; i ++) {
        if(min > prices[i]) {
            min = prices[i];
        } else {
            max = Math.max(max, prices[i] - min)
        }
    }
    return max;
}
 
122. 买卖股票的最佳时机 II
 
只要股票价格上涨，上涨的部分就是我的利润，可以理解为上涨期间第一天买入，然后一直持有到上涨最后一天即下跌前一天再卖出。
 
var maxProfit = function(prices) {
  let profit = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    if (prices[i + 1] > prices[i]) profit += prices[i + 1] - prices[i];
  }
  return profit;
};
 
好文：
 
小白带你学贪心算法！
 
js实现—加油站问题(贪心算法)
 
​

写在前面
 
在学习了这么多的视觉算法控制算法和编程算法之后，对整个算法体系有了一些感想，在这里记录一下。
 
算法是什么
 
很多人学习了很多算法，却根本不知道算法的本质是什么？但是深入说起来，这其实是一个哲学问题。
 有些书说算法是帮主我们解决问题的方法。但是问题是怎么来的呢？没错，问题也是人提出来的，用人设计的算法去解决人提出来的问题，就意味着一个前提条件，即问题所在的空间内要包含问题的解。
 接下来是传统算法和编程算法的区别，首先我把视觉统计控制什么之类的算法都归为传统算法，他们与编程算法最本质的区别就是，他们的解域都是无穷大的，编程算法是一定可以把所有可能结果都列出来的。
 比如，我们要找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次等很少的次数。假如我们把暴力算法写成状态矩阵的话，那么每次更新就需要遍历上一次状态表的全部维度，那么这个开销是很大的。而能使用动态规划解题的题目都是可以在有限步推导内求出新的状态转移矩阵元素目标值。
 思考为什么那么多题目都可以用动态规划去解题？因为按照哲学原理来说，世界上的问题的最优解应该是随机而平衡的。其实并不是动态规划更适合解题，而是人类的思维更适合动态规划，有些题目实际上是有更合适的求解算法的，然而大多数人想不到，人们只能想明白动态规划。因为人的大脑结构就跟动态规划很相似。
 而复杂状态更新方式的动态规划，我们称它为神经网络。