计算机科学是通过使用计算机解决各种问题的研究领域。
为了使用计算机解决给出的问题,您需要为其设计算法。
可设计多个算法来解决特定的问题。
提供了最大效率的算法应用于解决此问题。
算法的效率可通过使用合适的数据结构来改善。
数据结构帮助创建简单,可重用和易于维护的程序。
本模块允许学员选择并实现合适的数据结构和算法来解决特定的编程问题。
解决问题时算法和数据结构的作用
问题解决是每个科学规律的必要部分。
计算机广泛用于解决与各个域有关的问题,例如银行,商业,医疗,制造和运输。
为了使用计算机解决给出的问题,您需要为其编写程序。
程序由两个组件组成,即算法和数据结构。
算法这个词来源于波斯数学名称Al-Khowarizmi。
算法可定义为解决问题的逐步程序。
算法帮助用户在有限的步骤中到达正确的结果。
算法具有5个重要的属性:
有限性
明确性(确定目的)
输入
输出
有效性
只要可以为其编写算法,通过使用计算机可以解决问题。
此外,算法提供了以下好处:
帮助编写对应的程序
帮助区分一系列可以解决的小问题和难以解决的问题
决策制定成为更加理性的过程
使得过程一致和可靠
数据结构的作用
可使用不同的算法来解决相同的问题。
一些算法可能比其它算法更有效地解决问题。
应使用提供最大效率的算法来解决问题。
改善算法效率的其中一个基本技巧是使用适当的数据结构。
数据结构被定义为在内存中互相组织各个数据元素的方式。
数据可以按许多不同的方式来组织,因此,您可以创建尽可能多的数据结构。
经过多年已经证明很有用的一些数据结构是:
数据类型也是基本数据结构。
数组
链表
堆栈
队列
树
图
合适数据结构的使用有助于提高程序的效率。
使用合适的数据结构还允许您克服一些其它编程挑战,如:
简化复杂的问题
创建标准的可重用的代码组件
创建易于理解和维护的程序
数据结构的类型
数据结构可分为以下两类:
静态:例子——数组
动态:例子-链接表
设计算法时两个常用的技巧是:
分治法
贪婪法
分治法是解决概念性困难问题的强大方法。
分治法需要你找出一个方法:
将问题细分为子问题
解决微不足道的用例
组合到子问题的解决方案以解决原始问题
基于贪婪法的算法用于解决优化问题,其中您需要在给定的条件集合中最大化利润或最小化成本。
优化问题的一些示例包括:
找出从始发城市到一组目标城市的最短距离,给出两个城市之间的距离。
找出某个金额所需的货币票据的最小数值,其中有每个命名的任意票据数。
从给出的项集合中选择具有最大值的项,其中所选项的总重量不能超过给出的值。
递归:
递归指的是按照本身定义过程的技巧
用于解决本来重复的复杂编程问题
通过使用递归程序或函数,递归可以在程序中实现。递归程序或函数是调用本身的函数。
递归的主要好处是可用于编写清晰,简短和简单的程序
最简单的一个小例子:从前有座山,山里有个老和尚,…。
课间思考
明确在尝试找出前面n个自然数之和的以下算法中的问题:
算法:Sum (n)
1。s=n + (n - 1)和
2。返回(s)
答案:
在给出的递归算法中没有结束条件,因此,可以无限调用自身。正确的算法为:
1。如果(n=1)
返回(1)
2。s=n + (n - 1)和
3。返回(s)
确定算法的效率
影响程序效率的因素包括:
机器速度
编译器
操作系统
编程语言
输入大小
除了这些因素,程序的方式数据被组织且用于解决此问题的算法还对程序的效率具有重大影响。
通过确定消耗的资源量,可以计算算法的效率。
算法消耗的主要资源是:
时间:执行算法所需的CPU时间。
空间:执行算法时所用的内存量。
算法使用的资源越少,效率越高。
时间/空间权衡:
指的是您可以在程序执行速度较慢时可以减少使用的内存或在使用内存的成本很高时减少运行的时间。
可以应用时间/空间权衡的情形示例为数据存储。
