数据结构基础：算法的基础知识笔记

1、算法的概念

算法是问题求解过程中的精确描述，它为解决某一特定类型的问题规定了一个运算过程。

2、算法的特点

2.1 有穷性

一个算法必须在有穷的步骤结束后结束，并且每一步都在有穷时间内完成。

2.2 确定性

算法的执行过程中每一步都要有确定的定义，不能存在歧义。

2.3 可行性

算法应该是可以实现的，就是在有穷的步骤实现想要的结果。

2.4 输入

算法可以有零个或者多个输入，它作为初始数据为实现算法的结果提供初始量或被加工的数据对象。

2.5 输出

一个算法有一个或者多个输出，它们是与输入有特定关系的量。

3、优秀算法的特点

正确性、可读性、健壮性、效率高占用资源少。

4、算法描述的方式

4.1 流程图（Flow Chat）

流程图是最古老、流行最广泛的一种算法的图形表示法。每个算法都可由若干张流程图表示。流程图给出了算法中所进行的操作以及执行这些操作的逻辑顺序。

流程图的基本符号

求最大公约数

4.2 N/S 盒图

盒图是支持结构化程序设计产生的一种描述工具。分为顺序结构、选择结构、多选择结构 、while-do 循环结构、repeat-until循环结构，调用结构。

4.3 伪代码

用伪代码描述算法的特点是借助程序语言的语法结构 和自然语言描述，使算法具有良好的结构而又不拘泥于程序语言的限制。这样的算法易读易写，容易转换为程序。

4.4 决策表

决策表是一种图形表格，它可以将比较复杂的决策问题，简洁明了的方式呈现出来。如图：

5 、算法效率

算法效率是决定一个算法优劣的非常重要的一点，任何算法在计算机上执行都会消耗时间和存储空间资源。消耗时间和存储空间资源分别用时间复杂度和空间复杂度来体现。

语句频度：是指算法语句被重复执行的次数。

算法的执行时间：算法中各个基本语句的语句频度之和。

例如：语句频度为 1、n、n^2 时间复杂度分别为O(1) 常量阶、O(n) 线性阶、O(n^2) 平方阶。若三个是一个整体，算法的时间复杂度为 O(n^2)。