一.算法的定义
1.算法的概念
什么是算法呢?算法就是描述解决问题的方法.
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作.
而对于给定的问题,是可以有多种算法来解决的.如我们曾经遇到过的排序问题,就可以使用冒泡排序算法,选择排序算法,归并排序算法,插入排序算法,快速排序算法等多种算法来解决问题.
但是没有对于所有问题都通用的通用的算法,就像这世界上没有包治百病的药一样,一个算法只能解决一个或一部分特定的问题.
在算法的定义中,提到了指令,指令能被人或机器等计算装置执行.它可以是计算机指令,也可以是我们平时的语言文字.
为了解决某个或某类问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都完成特定的功能,这就是算法.
2.数据结构与算法的关系
在前面的数据结构绪论篇中我们介绍过数据结构的概念:
数据结构是指数据的组织方式和存储结构,它关注的是如何高效地组织和存储数据，包括数组、链表、栈、队列、树、图等.
而算法是指解决问题的一系列步骤和规则，它关注的是如何高效地解决问题，包括排序、查找、图算法、动态规划等。
数据结构的选择和设计直接影响着算法的效率和实现方式。
算法的设计和实现需要考虑数据结构的选择和使用，不同的数据结构适合不同的算法。
因此,数据结构和算法相互依存，数据结构为算法提供了基础和支持，而算法则需要根据数据结构的特点来设计和实现。合理选择和使用数据结构可以提高算法的效率和性能，而高效的算法也可以充分发挥数据结构的优势。
总之，数据结构和算法是紧密联系的，它们相互依存、相互影响，共同构成了计算机科学中重要的基础知识。
二.算法的特性
算法具有五个基本特性:输入,输出,有穷性,确定性和可行性.
输入
一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合.
尽管对于绝大多数算法来说,输入参数都是必要的,但对于个别情况,如打印"hello world!"这样的代码,不需要任何输入参数,因此算法的输入可以是0个.
输出
一个算法有一个或多个的输出,这些输出是同输入有着某些特定关系的量.
算法是一定要有输出的,或者说算法运行结束后一定要有一个结果,如果算法运行结束后没有输出,则相当于算法做功为0,没有任何用处.
有穷性
一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成.
在C语言最开始的学习阶段,我们常常会因为for循环的判断标准写错而导致程序陷入死循环,这样死循环的代码就是不满足有穷性的.并且这里的有穷性的概念不是纯数学上的,而应该是在实际应用当中合理的,可以接受的"有边界".
就像你不能写一个算法,计算机需要算10年才能得出结果,这确实在数学意义上是有穷了,但时间跨度太大,算法就没有什么使用意义了.
确定性
算法中每一条指令必须有确切的含义,读者理解时不会产生二义性.并且,在任何条件下,算法只有惟一的一条执行路径,即对于相同的输入只能得出相同的输出.
这个特性很好理解,即算法的每一步都必须不能有歧义.
比如你不能设计一个算法的指令是"你背着张三买一份薯条",这样的指令让李四执行,李四可能会躲过张三,在张三不知情的情况下买一份薯条,而这样的指令让王五执行的话,王五可能会把张三背在身上然后一起去买薯条.
这样的歧义毫无疑问将会导致算法在输入相同的情况下得到不同的输出结果,这就不符合算法的确定性.
可行性
一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的.
可行性意味着算法可以转换为程序上机运行,并得到正确的结果.
三.算法的设计要求
1.正确性
算法的正确性是指算法至少应该具有输入,输出和加工处理无歧义性,能正确反映问题的需求,能够得到问题的正确答案.
但算法的"正确"通常在通常在用法上有很大的差别,大体分为以下四个层次:
- 算法程序没有语法错误.
- 算法程序对于几组输入数据能够产生满足要求的输出结果.
- 算法程序对于精心选择的典型,苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果.
- 算法程序对于一切合法的输入数据都能产生满足规格说明要求的结果.
显然,对于这四个层次,第一层次的要求是最低的,但仅仅没有语法错误实在是谈不上是一个好的算法.而第四层次是最困难的,我们几乎不可能逐一验证所有的输入都得到正确的结果.
因此算法的正确性在大部分情况下都不可能用程序来证明,而是用数学方法证明的.
一般情况下,我们把第三层次的正确性作为衡量一个算法是否正确的标准.
2.可读性
算法设计的另一目的是为了便于阅读,理解和交流.
可读性高有助于人们理解算法,晦涩难懂的算法往往隐含错误,不易被发现,并且难于调试和修改.
举个例子,我在初学C语言的时候,有时会和同学比拼谁的解题代码更简短,往往会因此简略合并代码中非常多的细节和步骤,并且以此为荣.
但事实上这并不是一个好的代码风格,在团队协作的过程中,这样的代码是非常影响团队效率的,因为这样的代码可读性很差,不光影响他人,甚或时间一长,自己都不知道当时自己写的是什么了.
因此,可读性是算法好坏很重要的标志.
3.健壮性
当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果.
一个好的算法还应该能对输入数据不合法的情况做合适的处理.比如年龄和体重不应该是负数.
4.效率与低存储量需求
设计算法应该尽量满足时间效率高和储存量低的需求.
时间效率是指算法的执行时间,对于同一个问题,如果有多个算法能够解决,执行时间短的算法效率高,执行时间长的算法效率低.存储量需求指的是算法在执行过程中需要的最大存储空间,主要指算法程序运行时所占用的内存或外部硬盘存储空间.
在生活中,人们都希望花最少的钱,用最短的时间,办最大的事,算法也是这样的思想,我们在设计算法时,要尽量追求可以高效率低存储量的算法来解决问题.
结语
当我们搞清楚什么是算法后,在数据结构算法篇我们还将一起学习算法效率的度量方法,算法的时间复杂度及算法的空间复杂度相关的知识.希望这些内容能对大家有所帮助,一起学习,一起进步!
相关文章推荐
数据结构算法篇思维导图:
