当前课程知识点：数据结构 > 第1章 绪论 > 1.4 算法及其设计要求 > 讲解
这一节，我们来学习算法及其设计要求
首先，来看一下算法的概念。算法是指求解给定问题的步骤
一个算法
它具有以下的特性
首先是有穷性
是指算法
它的执行总次数是有限的
并且，每一步
是在有限的时间内完成
注意，这里的有限并不是数学上的有限
因为，数学上给出任意一个大的数
它都是有限的
这里不仅要有限
而且要合理
在可接受的时间范围内结束
不能说一个算法
跑了一年才跑完
尽管它是有限的
但不合理
第二
确定性。算法每一步所做的事情是确定的，不能有歧义
不像自然语言
自然语言，说出一句话
不同的人可能有完全相反的理解
这就是歧义。而算法当中每一步做的事情必须是确定的
第三
可行性，是指算法当中的每一步
在现有的技术条件下是可行的
不能说算法当中某一步是现有技术无法解决的问题
那不行
第四
至少有一个输入。注意，这里的输入不一定是指键盘的输入
而是泛指算法要处理的数据
比如，最简单的Hello World程序
其实，要输出到显示器的数据
Hello World，实际上也是一种输入
至少要有一个输出。任何算法
都要有一定的功能
无论是计算出了一些结果
还是中间做了某些操作
做了某些I/O
都至少会有一个输出
这里的输出也不一定是指将结果输出到显示器或者打印机
而是泛指
算法得到的结果或执行的操作
所以
我们经常把算法描述成一个黑盒
这个黑盒接收输入、产生输出
再来看一下算法的设计要求
设计出来的算法要达到什么样的目标
达到什么样的标准，才能称为一个好的算法
第一
正确性。一个算法所做的事情必须是严格满足问题要求的。这个很好理解，设计的算法
必须满足问题要求
也就是
能够正确地求解给定的问题
如果一个算法
连正确性都不能保证
就谈不上良好了
第二
可读性。一个算法应该是易于理解的。注意
这里的易于理解是相对的
通常来说
越难的算法，要解决的问题越复杂的算法
肯定不是那么容易读懂
所以，易于理解是相对的
比如，有两个算法解决同一个问题
那么，大多数人都能理解的那个算法很明显
它的可读性要好一些
再一个就是易于调试及扩展
这个主要是从工程角度来说的
比如，一个算法满足了当前的问题需求
将来，稍微将问题需求改一下
改动一点点
当前的算法只需要做很小的修改
就能满足新的需求
这就叫做可扩展性
从工程的角度来说
除了代码可读性之外
还比较强调可扩展性
能够以较小的代价满足新的需求
第三
健壮性
当算法接收的输入不合理
比较苛刻
甚至是恶意的时候
或者说，输入涉及到了算法的一些边界条件，这时候
你的算法应该能够正确地处理
这些不合理、恶意的、边界条件等等
而不能说，在接受不合理、恶意、边界条件的数据的时候
算法得到了非预期的结果
甚至直接崩溃
这不行
这就叫健壮性
能够处理各种各样的输入数据
第四点是高效率
在满足前三点的前提下
算法所耗费的时间越少越好
所耗费的内存越少越好
注意，这个高效率
有时候的优先级是高于可读性的
因为大多数时候，我们关心的是算法跑的够不够快
消耗的内存是不是够少
至于这个算法可不可读
这时候并不是很重要
因为，我们并不要求没有一点技术基础的人都能读懂这个算法
我们看重的是效率
刚才我们讲了算法的设计要求，那算法跟程序到底有什么样的区别呢
首先
可以用任何语言描述算法
因为算法并不是真正的程序
我们可以用自然语言，比如英语
汉语，可以用数学语言，还可以用伪码
这些语言
计算机都不理解，它们并不是真正的编程语言
甚至还可以用
只有你能读懂一些符号
比如，很多人在求解一道问题的时候
在纸上画的那些符号
那些求解的思路，实际上也可以称为算法
只是交流起来
别人可能读不懂
而程序
必须用计算机能够理解的语言
也就是所谓的编程语言
我们要想让算法在计算机上执行
必须把算法用编程语言写成真正的程序
这样，计算机才能够去运行你的算法
程序是算法的实现
可以用不同编程语言实现同一算法
我们之前讲过
对于这门课来说
你可以用任何你喜欢的编程语言去实现
任何一个算法
算法不能被计算机运行
而程序可以。刚才已经提到，程序是能够被计算机运行的，而算法不行
算法必须满足有穷性
刚才讲过，算法的一个标准之一就是在有限的时间内完成，而程序
却可以无限地运行下去
比如，我们平时使用的操作系统
Windows，只要不关机
只要不断电
它会无限地运行下去
而算法不行
必须要结束
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
