近似算法 假设现在需要解决一个NP-Hard问题，但是又不太可能在多项式时间内求解，但是我们可以退而求其次，那么就必须要牺牲下面的其中一项： 求得最优解 在多项式时间内完成 覆盖问题的所有例子 而牺牲第二条是不能接受的，当我们选择满足后两者（也就是牺牲第一项），即对解的优越性放宽要求时，设计出的算法被称为近似算法。 Load Balancing问题 给定\(m\)台相同的机器，\(n\)个任务

P、NP、NPC、NPH问题 P问题：存在多项式时间算法的决策问题。 NP问题 ：能在多项式时间内验证某个猜想答案的正确性，但问题求解可能在无法在多项式时间内完成。比如Composite问题、3-Satisfiability、Hamiltonian Cycle，很容易就确定一个答案是否正确，但确找不到一个公式来描述其规律。 结论1：P \(\subseteq\) NP 结论2：NP \(\subs

多项式规约 定义：若问题X 的任意实例可以由下面两条之和解决 问题X可以通过多项式时间的基本运算步骤转换为问题Y； 问题X多项式次调用求解问题Y的算法，且问题Y可以在多项式时间内被求解。 那么称问题X可以多项式规约到问题Y，记为 $ X _{p} Y $。需要注意的是，问题X转换为问题Y之后，问题Y的运行时间是建立在问题Y的输入上。 多项式规约的几个性质： 若 \(X \le_{p} Y\)

最小割 在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割。一个$ st-cut $即去掉的边把源点s和汇点t划分在两个不同的部分。 最小割定义 一般来说，一张图中有多个不同的\(st-cut\)，如下图便为其中一个 \(st-cut\) 。 一个割例子 但是在实际应用中，我们去掉每条边往往都是有代价的，以边的容量作为权值，一个割中去掉的边的权值之和为这

Git撤销commit命令 当要撤销的提交不是最开始的提交时 1git reset HEAD~ 当要撤销的提交时最开始的提交时 1git update -ref -d HEAD ## Git连接远程仓库 1git remote add origin url 注：url为github仓库链接 ## Git删除已经add的文件 1.要删除的文件少时 一种是 git rm --cached "文件路径"

希腊字母 小写字母 语法 大写字母 实现 \(\alpha\) \alpha \(A\) A \(\beta\) \beta \(B\) B \(\gamma\) \gamma \(\Gamma\) \Gamma \(\delta\) \delta \(\Delta\) \Delta \(\epsilon\) \epsilon \(E\) E \(\varepsi

本文大部分转载自知乎@阮行止，后添加了自己的一些思考。 1. 从一个生活问题谈起 先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。 依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+

红黑树 红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。 红黑树的性质 每个节点要么是黑色，要么是红色。 根节点是黑色。 每个叶子节点（NIL）是黑色。 每个红色

胜者树与败者树是完全二叉树。就像是参加比赛一样，每个选手有不同的实力，两个选手PK,实力决定胜负，晋级下一轮，经过几轮之后，就能得到冠军。不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。 胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。 胜者树 胜者树的一个优点是，