当前位置：首页> 安全验证

安全验证

时间：2023-10-24 20:35:31 下载该word文档

算法学习报告

学习总结：
对于算法这门课，要善于给出算法的形式化表示，学会用一些算法分析的数学基础，原来的时间复杂度的分析，一般是采用一些数学的方法，有的时候计算起来比较繁琐，对于形如T(n=a*T(n/b+f(n的递归方程，主定理的使用，只需要比较f(n与n^longba的量级即可，可以快捷地求出时间复杂度的量级，同时我们还得到了如何改进有关算法的一些提示，当n^longba起主导作用时，可以从减少子问题的个数和减小子问题的规模两个方面来考虑，而当f(n起主导作用时，这时候要着重改善子问题分解组合时的处理方法。
算法常用的技术有分治法，贪心法，周游法，回朔法，动态规划法，分支定界法。
分治法的要领就是将一个规模较大的问题分解为若干个规模较小的子问题，这些子问题与原问题同类。其分治法的精髓就是分、治、合。利用分治法可以解决求第k小元素问题，其主要思想是当元素个数小于50时可以用堆排序找到，但是当元素个数大于50时，五分化中项的中项m,将数组分成三部分，比它大的，比它小的以及与它相等的。寻找最近点对的问题，采用分治法的方法是将点对平分到两个部分，分治求出左半部分的最近点对，右半部分的最近点对，再求出点位于左半和右半的最近点对，为了减少比较的次数用到了检查落到带状区域内的每一个点检查其后的4个点。

动态规划法与分治法类似，但是有着不同，动态规划法解决的问题通常具有以下几个特点：最有子结构和高度的重复性。动态规划的指导思想是：在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。如果二维数组中有相当一部分元素在整个计算过程中都没有用到则可以采用动态规划的变形—备忘录的方法，比如说是求解LCS问题；其他的一些动态规划问题比如说矩阵连乘、最优二分搜索树无需计算的子问题只有少部分或全部都要计算，采用递推的方式比较好。
平摊分析收益手法（聚集方法，会计方法和势能方法）的引入，从整体上考虑时间复杂度而不是逐一的考虑每条指令的执行所需要的时间复杂度，聚集方法的关键在于找到如何分类，分别计算每类的耗费，再将耗费相加。会计方法的切入点一旦找到，计算起来非常方便，难点在于如何找到，而势能方法的切入角度比较好找：数据结构和势函数。
集合操作中的一些讲解给出了一些思想的启示，内部名外部名的使用，减少了改名的次数，更是惊叹于脱线MIN问题的解决思路，用集合名（数字）来表示删除i的E指令序号，其关键在于Find指令和Union指令的使用。为了求出各点在原先树的正确深度，又使时

阅读全文