computer science

algorithm

算法是解决某一特定问题的一组有穷规则的集合。在计算机中就是一组有穷指令的有序排列。

  1. 特征

    确定、有穷、输入、输出、可行。

  2. 算法描述

    就是告诉别人算法的原理。可以通过自然语言、流程图、伪代码、程序设计语言。

算法类型

  1. 穷举法

    简单暴力,列举所有可能情况。有密码学的暴力破解法,四色定理的证明。

  2. 回溯法

    一种选优搜索法,按选优条件向前搜索,以达到目标。在搜索过程中,能进则进,不能进则退回来,换一条路再试,通过此种方式提高搜索效率,减少不必要的测试。例如迷宫问题、网络爬虫、八皇后问题。

  3. 递归算法

    直接或者间接掉哟个自身的算法。递归思想就是用与自身问题相似但规模较小的问题来描述自己。例如欧几里得算法、斐波那契数列。有兴趣可以了解一下德罗斯特效应。

  4. 分治法

    将一个难以直接解决的大问题,分解成一些规模较小的子问题,以便各个击破,分而治之。如果子问题还比较大,可反复使用分治算法,直到最后的子问题可以直接得出它们的结果。由于分治算法的子问题类型常与原来的相同,因而很自然地使用递归算法。例如二分查找。

  5. 贪心法

    将待求解的问题分解成若干个子问题进行分步求解,且每一步总是做出当前最好的选择,即得到局部最优解,再将各个局部最优解整合成问题的解。例如田忌赛马,当然面试官也是利用贪心法选人的。

  6. 动态规划

    动态规划是解决多阶段决策最优化问题的一种方法。同样需要递归式,不过规则就是将每一次决策阶段的结果都存起来,也许下一次决策需要用到该决策结果。

算法评判标准

  1. 正确性

    一个正确的算法是对每一个输入数据产生对应的正确结果并且终止。而错误的算法对于某些输入数据要么不会终止,要么在终止前给出的不是预期的正确结果。

  2. 复杂性

    好的算法有较低的复杂度,复杂度分为时间复杂度和空间复杂度。时间复杂度看指令数,空间复杂度看所需存储空间。