算法--基础

学习算法设计的重点就是把人类找到的求解问题的方法、步骤以过程化、形式化、机械化的形式表示出来，以便让计算机执行。

算法概述

定义

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

要素

算法由操作、控制结构、数据结构3要素组成。

• 操作 类型说明算术运算加、减、乘、除关系比较大于、小于、等于、不等于逻辑运算与、或、非数据传输输入、输出、赋值
• 控制结构 类型说明顺序结构各操作是依次执行的选择结构由条件是否成立来决定选择执行循环结构操作重复执行，直到满足某个条件时才结束
• 数据结构：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。

基本特征

算法具有五个重要特征：有穷性、确切性、输入项、输出项、可行性。

• 有穷性：必须能在执行有限个步骤之后终止；
• 确切性：每一步骤必须有确切的定义；
• 输入项：有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
• 输出项：有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
• 可行性：任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。

算法的质量指标

• 正确性：合法的输入数据得出满足要求的结果；
• 可读性：代码易于理解，晦涩难懂的算法易于隐藏较多错误而难以调试；
• 稳健性：充分考虑异常情况，并且处理出错的方法不能中断算法的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理；
• 高效率与低存储量：不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
  • 空间复杂度：算法在运行过程中临时占用存储空间大小的量度；
  • 时间复杂度（Asymptotic Time Complexity）：算法的运行时间。 算 法 运 行 时 间 = ∑ 原 操 作 的 执 行 次 数 ∗ 原 操 作 的 执 行 时 间 算法运行时间 = ∑原操作的执行次数 * 原操作的执行时间 算法运行时间=∑原操作的执行次数∗原操作的执行时间 对于复杂的算法计算运行时间，工作量很大。所以经常采用：最深层次循环体内的语句中的原操作。 分类：O(1)常数级、O(logn)对数级、O(n)线性级、O(nc)多项式级、O(cn)指数级、O(n!)阶乘级。

深入思考：P问题、NP问题及NPC问题：

• P问题：所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；
• NP问题：所有可以在多项式时间内验证它的解是否正确的决定问题组成，或者等效的说，那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合；
• NPC问题：NP完全问题，是NP的一个子集，且其中每一个问题均能由NP中的任何问题在多项式时间内转化而成。如，背包问题、华容道游戏（由于搜索）等

补充： 确定型图灵机：同一个输入，按照惟一确定的方式进行运行。

算法描述

算法的方式主要有：自然语言、流程图、盒图、PAD图、伪代码和计算机程序设计语言。

• 自然语言：日常所用语言，描述语句较长且容易产生歧义性；
• 流程图：不易表述数据结构，层次感不强；
• 盒图：不易扩充和修改，对于大型复杂算法较难描述；
• PAD图：图形符号书写、编辑、录入不方便；

求解步骤

在这里插入图片描述