2017-11-21

算法-基础

基础概念

算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

程序是算法用某种程序设计语言的具体实现。算法必须可终止，程序却没有这一限制。即：程序可以不满足算法的性质(5)—“有穷性”。 算法+数据结构=程序

它的五个特征如下：

• 输入：算法有零个或多个输入量；
• 输出：算法至少产生一个输出量；
• 确定性：算法的每一条指令都有确切的定义，没有二义性；
• 能行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；
• 有穷性：算法必须总能在执行有限步之后终止。

算法分类

• 贪心法

• 动态规划法

• 分治法

• 状态空间树搜索算法

  使用剪枝函数

  • 回溯法——在状态空间树上找出满足约束条件的所有解
  • 分支界限法——求解目标是找出满足约束条件的一个解/在满足约束条件的解中找出最优解
    • FIFO分支界限法
    • LIFO分支界限法
    • LC分支界限法

算法间的异同

动态规划法与分治法的异同：

共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解

不同点：1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。

动态规划法与贪心法的异同：

共同点：都是求解最优化问题；都要求问题具有最优子结构性质。

不同点：1、求解方式不同：动态规划法：自底向上；贪心法：自顶向下。以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

2、对子问题的依赖不同：

动态规划法：依赖于各子问题的解，所以只有在解出相关子问题后,才能作出选择；应使各子问题最优，才能保证整体最优；

贪心法：不依赖于子问题的解。仅在当前状态下作出最好选择，即局部最优选择，然后再去解作出这个选择后产生的相应的子问题。

具有最优子结构性质的问题有些只能用动态规划法，有些可用贪心法。

分枝限界法与回溯法的异同：

共同点：都是在问题的状态空间树上搜索问题解的算法。都用活结点表实现, 都可用约束函数剪去不含答案结点的分枝, 都可用限界函数剪去不含最优解的分枝.

不同点：求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有可行解；而分支限界法的求解目标则是找出满足约束条件的一个可行解，或某种意义下的最优解。

搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或最小耗费优先的方式搜索解空间树。

合并排序与快速排序比较：

问题分解过程：合并排序——将序列一分为二即可。 （十分简单）

快速排序——需调用Partition函数将一个序列划分为子序列。（分解方法相对较困难）

子问题解合并得到原问题解的过程：

合并排序——需要调用Merge函数来实现。（Merge函数时间复杂度为O(n)）

快速排序——一旦左、右两个子序列都已分别排序，整个序列便自然成为有序序列。（异常简单，几乎无须额外的工作，省去了从子问题解合并得到原问题解的过程）

算法之路

• 第一阶段：对于某一个具体的算法，首先要搞清楚这个算法解决的问题是什么，可能是实现一个具体的功能，也可能是在某些方面，比如时间复杂度或者空间复杂度方面很卓越，总之搞清楚这个算法被研究出来的目的是什么。
• 第二阶段：然后就要弄清楚这个算法的生存环境了，也就是看看你此时研究的东西是不是对别的知识有依赖，应该先把底层依赖的知识理解并掌握。这些问题都解决之后，就进入到算法本身的学习，理解一个算法是一件辛苦的事情，刚开始看必然会产生很多的困惑，比如经常会怀疑作者讲述的内容的重要性？这些内容和这个算法有什么联系呢？经常会有这种摸不着头脑的感觉，其实作者做的铺垫都是为了建立起描述算法主要内容的基础，只有接受和理解这些基础，才能逐渐触碰到算法的精髓，所以耐心是很重要的。
• 第三阶段：算法的主要过程看完之后，往往还是会感到困惑，主要是不知道这个过程好在哪，这就进入了下一个阶段，理解作者对这个过程在功能性或者效率卓越这件事上的解释和证明。这才真正触碰到算法最精髓的部分，也就是深度的理解算法的主要过程所带来的好处，这才是最锻炼人理解能力的地方。
• 第四阶段：上面几点是算法学习阶段的过程了，接下来就是研究算法的代码实现，自己设计测试用例亲自跑一下代码，以及从代码运行时间的角度分析这个算法的优势，这也是加深对算法的理解的过程。
• 第五阶段：最后是配合相应的题目练习，让自己通过题目练习的方式，会用、善用学习到的算法，并对这个算法产生一定的敏感程度，具体是指看到某些题目时，能够根据题目的特点，产生与该算法的对应，也就是具备举一反三的能力。

dzzxjl