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

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

Scroll Down


1、算法的概念
算法是问题求解过程中的精确描述,它为解决某一特定类型的问题规定了一个运算过程。
2、算法的特点
2.1 有穷性
一个算法必须在有穷的步骤结束后结束,并且每一步都在有穷时间内完成。
2.2 确定性
算法的执行过程中每一步都要有确定的定义,不能存在歧义。
2.3 可行性
算法应该是可以实现的,就是在有穷的步骤实现想要的结果。
2.4 输入
算法可以有零个或者多个输入,它作为初始数据为实现算法的结果提供初始量或被加工的数据对象。
2.5 输出
一个算法有一个或者多个输出,它们是与输入有特定关系的量。
3、优秀算法的特点
正确性、可读性、健壮性、效率高占用资源少。
4、算法描述的方式
4.1 流程图(Flow Chat)
流程图是最古老、流行最广泛的一种算法的图形表示法。每个算法都可由若干张流程图表示。流程图给出了算法中所进行的操作以及执行这些操作的逻辑顺序。
流程图的基本符号
1111.jpg
求最大公约数
1112.jpg
4.2 N/S 盒图
盒图是支持结构化程序设计产生的一种描述工具。分为顺序结构、选择结构、多选择结构 、while-do 循环结构、repeat-until循环结构,调用结构。
1113.jpg
4.3 伪代码
用伪代码描述算法的特点是借助程序语言的语法结构 和自然语言描述,使算法具有良好的结构而又不拘泥于程序语言的限制。这样的算法易读易写,容易转换为程序。
4.4 决策表
决策表是一种图形表格,它可以将比较复杂的决策问题,简洁明了的方式呈现出来。如图:
image.png
5 、算法效率
算法效率是决定一个算法优劣的非常重要的一点,任何算法在计算机上执行都会消耗时间和存储空间资源。消耗时间和存储空间资源分别用时间复杂度和空间复杂度来体现。
语句频度:是指算法语句被重复执行的次数。
算法的执行时间:算法中各个基本语句的语句频度之和。
例如:语句频度为 1、n、n2 时间复杂度分别为O(1) 常量阶、O(n) 线性阶、O(n2) 平方阶。若三个是一个整体,算法的时间复杂度为 O(n^2)。