算法

算法简介

  1. 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰 指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的 输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执 行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样 的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

  2. 算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初 始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。一个 状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机 输入。

  3. 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有 效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和 斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇 于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵 1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。

算法5个特性

  1. 有穷性

    1. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
  2. 确切性

    1. 算法的每一步骤必须有确切的定义
  3. 输入项

    1. 一个算法有0或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件
  4. 输出项

    1. 一个算法有一个或多个输出,以反映对输入数据加工后的结果,没有输出的算法是毫无意义的
  5. 可行性(有效性)

    1. 算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成

算法2要素

  1. 数据对象的4种运算和操作

    1. 算术运算

    2. 逻辑运算

    3. 关系运算

    4. 数据传输

  2. 算法的控制结构

算法评定5标准

  1. 时间复杂度

  2. 空间复杂度

  3. 正确性

  4. 可读性

  5. 健壮性

算法思想

  1. 递推法

  2. 递归法

  3. 穷举法

  4. 贪心算法

  5. 分治法

  6. 动态规划法

  7. 迭代法

  8. 分支界限法

  9. 回溯法

算法3大类

  1. 有限的,确定性算法

  2. 有限的,非确定算法

  3. 无限的算法

经典算法举例

  1. 欧几里德算法

  2. 割圆术

  3. 秦九韶算法

@耿志环 2012-∞ 冀ICP备17033181号, powered by Gitbook修订: 2018-08-16 15:51:00

results matching ""

    No results matching ""