数据结构与算法入门之算法基础:确定性、健壮性、有穷性、正确性

2022-07-1710:57:16数据结构与算法Comments2,895 views字数 984阅读模式

1. 算法的特性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

1) 输入输出文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

算法具有零个或者多个输入,同时,算法具有至少一个的输出。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

对于在屏幕上打印”Hello World”一样,你可以不需要有任何的输入,直接输出得到结果即可,而对于一个没有输出的算法,没有任何意义文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

2) 确定性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

算法的每一步都具有确定的含义,无二义性。任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得到相同的输出。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

请注意,如果算法的目的是产生一个随机数字,每一次运行产生了不同的结果,看上去好像违反了算法确定性原则,但计算机产生随机数亦是使用一种(或多种)算法解决,以线性同余产生随机数为例,其利用了CPU时间的不同产生的不同的结果,当CPU的时间完全一样的时候依旧会产生相同结果,只不过人类无法察觉到如此精确的时间区别。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

3)有穷性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

一个算法总是需要(输入合法的情况下)在有限的步骤结束,即每个算法需要在有穷的时间内完成。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

这是算法与程序的最主要的区别,程序可以无限制循环的执行下去。对于此,你可以理解为一个算法必须要有一个”边界“,即使一个算法需要计算机连续运算50年,但依旧是有穷的,只不过这个算法意义已经不是很大了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

4)可行性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

一个算法是可以被执行的,即算法中的每个操作都可以通过已经实现的基本运算执行有限的次数完成。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

尽管在目前计算机解存在着没有实现成功的极为复杂的算法,但是并不能说的上是无法实现,只不过是受到现在的工具和人类的大脑限制了,这属于理论研究的范围。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

2. 算法设计要求文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

1) 正确性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

正确性(Correctness)指的是该算法能够满足预先指定的功能与性能的需求,即能够得到正确答案。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

其大致可以分为以下四点:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

a)该算法中不含任何语法错误。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

b)程序对于几组输入数据能够得到满足需求的结果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

c)程序对于非法的输入也能够得到满足需求说明的结果(如抛出异常)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

d)程序对于精心挑选的严苛数据依旧能够产生满足需求的结果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

2)健壮性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

健壮性(Robustness)指的是当输入数据不合法时,算法也能做出相关的处理,而不是产生不可预计的效果。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

3)可读性文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

可读性(Readability)指的是算法是可以阅读,理解和交流的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

4)耗时低,占用空间少文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

运行时间(Running time)与占用空间(Storage space)概念,在设计算法时,我们总是希望能够更少的使用时间和空间达成我们的目标。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

我们算法与数据结构的研究的重点就是为了让程序运行块,占用空间低。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25025.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25025.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定