算法设计与分析学习总结
通过对《算法设计与分析》这门课的学习，似乎对算法有了一定的了解，之前对算法并没有太多的接触，只是一些普通的编程。选课的时候，觉得特别有意思，就选了这门课，通过学习各类算法，有了一定的认识。递归法，分治法，蛮力法，回溯法。贪心算法等等，对之后的编都有很大的帮助。
现在，我深刻的明白这门课的对软件工程专业的重要性，程序的编写都离不开它，对培养思维能力也有一定的帮助，还能培养我们思考分析、解决问题的能力。对于一个问题，运用不同的算法都会有不同的解决方法，空间复杂度和时间复杂度都不太相同，合适的算法能更加高效，更加便捷的完成问题。算法可以用自然语言，伪代码，流程图等来描述，各种程序设计，软件设计，数据库设计，系统设计归根到底都要用算法来完成。
在课堂上，老师讲的各种方法，虽说有一些不太理解，经过课后的学习，也有了一定的认识，结合课后作业，每一题都是对每一种算法针对性的练习，巩固了所学知识。因为专业所学的编程语言就是java，所以都是运用Java语言来实现的，对其他语言没有去深入了解，应该也都是差不多的解决问题。现阶段学习到的都是算法的一些皮毛，之后会继续深入学习，体验其中的奥妙。
接下来是一些方法的理解，其中包括课堂学过的各种方法。
**递归法：**能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
**分治法：**对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。分治法在每一层递归上都有三个步骤，1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；3.合并：将各个子问题的解合并为原问题的解。
**蛮力法：**也称为穷举法或者枚举法，它是算法设计中最常见的方法之一。蛮力法的基本思路是问题的所有可能状态一一测试，直到找到解或者全部可能状态都测试为止。蛮力法的有点有很多例如应用范围广，不受实例规模的限，当要解决的问题低频率出现，并且高效算法很难设计时可选蛮力法，对解决一些小规模问题实例仍然有效，可作为衡量其他算法的参照物等等。
**回溯法：**是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 运用回溯法解题的关键要素有三点，1.针对给定的问题，定义问题的解空间；2.确定易于搜索的解空间结构；3.以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
**分枝限界法：**是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分枝限界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
**贪心算法：**指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。贪心算法的过程：1.建立数学模型来描述问题；2.把求解的问题分成若干个子问题；3.对每一子问题求解，得到子问题的局部最优解；4.把子问题的解局部最优解合成原来解问题的一个解。例：设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1），步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r1)/b(q1+1），步骤三：重复步骤2，直到分解完毕。
**动态规划算法：**将待求解的问题分解为若干个子问题，先求解子问题，然后从这些子问题得到原问题的解。经动态规划法得到的子问题往往不是相互独立的，为了避免重复计算，我们可以用一个表来记录所有已解决的子问题的答案。它常用于求解具有最优子结构性质（问题的最优解包含了子问题的最优解）和子问题重叠性质（在用递归算法自顶向下的解决问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次）的问题。基本步骤：1.找出最优解的性质，并刻画其特征；2.递归地定义最优值；3.以自底向上的方式计算出最优值；4.根据计算最优值时得到的信息，构造一个最优解。
除此之外还有很多的算法，暂时没有深入去了解和学习，通过以上是多种算法的描述,明白了算法是对问题的模型化，求解的算法化和设计最优解。对于繁琐的计算机问题有了一定的解决方法，算法这门课也对我的学习起到了承前启后的作用，大二学习数据结构，对编程有了一定的了解，结合算法分析，假以时日，对我的编程能力一定有很大的帮助，对数据库的学习也有很大的帮助，以上便是我对《算法设计与分析》这门课的学习心得。
2019.12.11
广理丶小泽