程序员不要跟算法过不去！算法技术总结
算法
也就是说，使用计算的思想，方法，工具和技术来解决问题的思想和方法。计算机提供计算功能和硬件设施；算法提供计算思想和软件技术，以更好地实现计算机的潜力。
有人说算法没有用。这种观点就像一个盲人说，如果他看不到花朵盛开，世界上没有花。无论如何，有眼睛的人都很难接受。
让我们举一个简单的例子：
如果您想对1,000,000个记录进行排序，您的计算机每秒可以处理1,000,000个记录。
如果选择快速的o（nlogn），则花费在log2（1000000）= 20s的时间；
如果选择插入的o（n^2），则需要大约1000000^2/1000000 = 100000S = 11.57天；
如果选择xx的o（n^3），则大约需要100000^2 = 31709.791年。
显然，拥有子弹的人不如拥有导弹的人那么好，而拥有导弹的人不如拥有核弹的人那么好。您很容易知道谁是未来世界的国王。
算法大师Knuth曾经说过：“ ...算法是一种一般智能工具，可以帮助了解各种学科的知识...只有向计算机教授知识，您才能真正理解知识……与对问题的常规理解相比以算法形式的知识将使理解更加深刻……”
因此，算法不仅可以确定统治世界的国王（除非您破坏世界上所有的计算机），还可以帮助个人学习和理解知识，甚至了解生活；算法可以帮助有效地学习工作。
现在，让我们整理出常用的算法设计技术！
1。划分和处理方法：
将问题实例p（n）分解为B子问题实例P（n/b），需要解决子问题。然后合并子问题的解决方案，以获取针对原始问题的解决方案。
简而言之，它的意思是“分割和组合”。
例子：
①排序：首先将列表分为几个子名单，分开对它们进行排序，然后将其合并。
- 合并和分类的关键在于“组合”的过程；
②快速排序：在列表中选择一个元素并将其放在列表中，以便将列表分为两个小于元素而不小于元素的子名单。
然后，分别重复两个子列表的上述步骤，直到整个列表被排序为止。
- 快速分类方法的关键在于“分隔”的过程。
③二进制树遍历：分别横穿根节点，左子树和右子树。
- - 分裂和递归的自然特征。
分裂和治疗方法的效率：
t（n）= at（n/b） + f（n），其中f（n）是在“分隔”或“组合”过程中花费的时间。
对于合并排序，F（n）是将两个有序列表合并到较大有序列表中的时间；对于快速排序，F（n）是选择拆分元素并将其放入最终位置所需的时间。
根据主要定理：让f（n）= o（n^d），
①当d> log（a）/log（b）时，t（n）= n^d;
②当d = log（a）/log（b）时，t（n）=（n^d）log（n）
③当d <log（a）/log（b）时，t（n）= n^（log（a）/log（b））
实际定理实际上很容易记住：通过比较AT（N/B）和F（n）的效率获得t（n）的效率，其中AT（N/B）的效率可以视为： n^（log（a）/log（b）），只需比较功率数并获取较大的功率。
将问题示例分为两个子问题示例的常用方法，其尺度大致相等。
根据主要定理：
t（n）= 2t（n/2） + o（c），c是常数--------------T（n）= o（n）
t（n）= 2t（n/2） + n ----- t（n）= o（nlog2（n））
T(n) = 2T(n/2) + n^2 ------------------- T(n) = O(n^2)
可以看出，f（n）也起着非常重要的作用。 F（n）不能太大，最好是线性，否则，使用分隔和治疗方法的效率可能不高。合理采用分区和征服方法的效率通常应达到O（NLOG2（n）），并且至少应比采用其他算法技术的效率高一个水平。
2。还原处理方法：
当a = 1时，也就是说，当t（n）= t（n/b） + f（n）时，划分和治疗方法将退化为减少的治疗方法。目前，F（n）的大小具有非常重要的影响。
减法治疗有三种形式：
①减去常数：t（n）= t（nb） + f（n），例如
t（n）= t（n-1） + c，c是常数------ t（n）= o（n）
t（n）= t（n-1） + n -------------------t（n）= o（n^2）
减去常数的示例：插入排序----- t（n）= t（n-1） + n t（n）= o（n^2）
②降低因子：t（n）= t（n/b） + f（n），例如
t（n）= t（n/2） + c，c是常数------ t（n）= o（log2（n））半精细搜索
T(n) = T(n/2) + n ---------------- T(n) = O(n^2)
③减去可变大小：例如，找到最大的常见分裂GCD（m，n）= gcd（n，m％n）
简而言之，当使用划分或减法的方法时，应合理地分配子问题，并且分配和协调的过程应尽可能简单，以保持F（n）线性。通过这种方式，可以实现分裂和减法和减法方法的效率。 。
3。动态编程方法
动态编程方法的解决方案通常具有以下递归形式：s（n）= g（s（ni），f（n））i = 1,2，...，n，其中s（ni）和s（ NJ）通常是重叠的子问题S（nk），k> i，k> j。目前，基于内存函数的自下而上迭代方法或递归方法可用于构建解决方案s（1），s（2逐步），…，s（n）。
由于避免重复针对子问题的解决方案，因此动态编程方法显示出相对较高的效率。
动态计划方法与分裂和治理方法之间的差异：子问题示例除以分区和治理方法通常不会重叠子问题示例，而子问题示例则除以动态计划方法通常重叠，并且动态计划方法是最重要的。最佳解决方案通常包含子问题实例的最佳解决方案，因此最终的最佳解决方案可以逐渐从子问题实例的最佳解决方案构建。
动态编程方法的典型示例：查找斐波那契序列，查找二项式系数，背包问题，最长的子序列问题和矩阵乘法问题。
4。更改治疗方法
治疗方法的变化是基于问题转化的想法，将所需解决的问题示例转换为更特殊的问题示例，或者已解决的其他问题示例。治理的变化需要对问题之间的联系特别洞察力。
典型的变化方法包括预选。首先对待处理列表进行排序，然后进一步处理有序列表。
例如，如果使用顺序搜索，则需要O（n）时间，然后先排序然后以二进制查看，至少需要O（NLOG2（n））。显然，预选似乎是多余的。
但是kaiyun官方网站登录入口，如果您想进行多次搜索，则预分类开始起作用。假设您想搜索1000个记录C次kaiyun全站网页版登录，然后CN> NLOG2（n） + Clog2（n），n = 1000可以解决以获取C> 10。
也就是说，仅搜索十次以上，预选开始就开始起作用。
可变处理方法的另一个简单示例是解决最小常见的多重LCM（M，N）。
如果您知道lcm（m，n）= m*n/gcd（m，n），gcd（m，n）是最大的常见分裂，并且有一个非常有效的欧几里得算法，那么这个问题似乎很容易。
前提是您必须拥有丰富的知识和良好的见解。对于此问题的最简单算法是从1、1、2，...，N，一个一个一个一个逐一计算一个算法，直到可以被m和n分组为止。效率为O（MN）；一种更好的算法是采用最大数字max = max = max（m，n），从1开始，每个算法乘以每个，最大，2max，...，...，kmax，直到可以将其除以n。 ，效率为O（min（m，n））。
使用可变处理方法通常可以取得意外的结果。我们必须擅长问题分析并改变问题。
5。时间和空间权衡
时空折衷是基于“丰富空间和廉价时间，宝贵时间”和“极有限的空间和低时间要求”的想法，要么牺牲时间效率，要么为需求牺牲时间空间。前者在桌面PC字段中更为常见，而后者在微控制器和嵌入式产品等产品中更为明显。
典型的例子：
计数排序：使用数组存储比元素更大或更小的元素数量，并根据这些值确定元素在最终列表中的位置。
哈希方法：使用阵列和链接列表的组合来实现有效的词典。首先，使用一些哈希函数哈希（x）基于基于哈希表哈希台的相应位置的密钥映射记录[hash（key）]。如果存在冲突（多个密钥的记录被映射到同一底部），则将附加到下标的链接列表用于存储冲突的记录。这也是一个深刻的例子，说明如何通过显示应用程序来产生数据结构的强大组合。
递归/非追回性遍历：使用其他堆栈或标签存储在遍历过程中遍历的元素，从而避免重复遍历。
6。贪婪的技术
始终从当前可行选择中选择局部最佳部分解决方案，然后逐步构建最终解决方案。
贪婪的技术逐渐为最佳解决方案构建了三个条件：
1。可行：满足问题的限制
2。局部优化：当前可行的选择中始终选择局部最优的部分解决方案。
3。不可撤销：做出选择后，它是不可撤销的。
贪婪技术的典型示例：用于查找硬币，最小跨越树和Kruskal算法的PRIM算法，Dijskra算法的最短路径的Dijskra算法。
7。蛮力法
不要低估蛮力法。尽管这种解决方案通常不切实际，但始终可以使用蛮力方法找到解决方案。蛮力方法的目的是找到解决方案然后改进解决方案。蛮力方法有时会带来惊喜。
例如，子字符串匹配的蛮力版本（判断子字符串模式是否包含在string中），其最差的效率为o（mn），平均效率为o（m）kaiyun全站登录网页入口，m，m，n是str和模式分别。长度。换句话说，蛮力版本的匹配算法更实用。
蛮力方法的典型示例：用于布置和组合问题的耗尽的搜索方法。
8。迭代改进
迭代改进方法始终首先找到可行的解决方案，然后通过一些小型和局部变化来改善这种可行的解决方案，以使其倾向于最佳解决方案。迭代改进的关键是稳定性和收敛性。
迭代方法的典型示例：数值算法，遗传算法
9。回溯方法
回溯方法是详尽搜索方法的改进版本。详尽的搜索方法通常首先列出所有候选解决方案，然后找到根据目标问题满足要求的解决方案或最佳解决方案。回溯定律有点“智能”，逐步构建解决方案的组成部分。一旦有一个不可行的组件，路径就不会清楚，您将立即改变道路。回溯方法通常基于问题构建状态树，并通过遍历状态树的节点来解决它。叶节点不表示溶液或可行溶液。
回溯方法的典型示例：n女王的问题，图形深度遍历
10。分支划界技术
分支划界技术与回溯方法非常相似。由于我还没有学到这一点，所以我现在不会讨论它。分支划界技术通常用于解决优化问题。
11。找到近似解决方案
这是获得第二好的选择。如果您可以通过花费20分钟来解决旅行者问题的实用解决方案，那么是否有必要再花十个小时才能提高解决方案的0.1％？对于理论工人来说，确实是这样。但是，如果我是一个实用的工人，我会选择前者。学会权衡投资/回报率。
结论：
算法，应用算法的摘要。算法应该是计算机科学的灵魂和基石。无论是硬件还是软件，无论是专业还是生活，算法都无处不在。
您不能仅仅因为您暂时无法使用它而贬低其价值。实际上，这是掩盖耳朵并偷铃的一种方式。如果您不使用它，其他人将始终使用它，而其他人则可以体验到乐趣并获得致富的回报。永远不要与算法相处。
=================================
Shangxuetang-无软件开发时间
Java ｜ android ｜网络前端
注册礼物：
1。获得1,000元的奖学金
2。获取价值数万人民币的视频教科书
3。七天免费试用
免费试用时间：
星期二，星期四，星期六
班级位置：
西安省Xi'an软件公园的Tianze大楼五楼
