什么是算法和数据结构?
你可能会在一些教材上看到这句话:
程序 = 算法 + 数据结构
算法(Algorithm):是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。(任何代码片段都可视为算法)
数据结构(Data Structures):是计算机存储和组织数据的一种方式,可以用来高效地处理数据。
什么样的程序才是好的程序?好的程序设计无外乎两点,"快"和"省"。"快"指程序执行速度快,高效,"省"指占用更小的内存空间。这两点其实就对应"时间复杂度"和"空间复杂度"的问题。
举个例子:二分查找就是一个非常经典的算法,而二分查找经常需要作用在一个有序数组上。这里二分就是一种折半的算法思想, 而数组是我们最常用的一种数据结构,支持根据下标快速访问。很多算法需要特定的数据结构来实现,所以经常把它们放到一块讲。
实际上,在真正的项目开发中,大部分时间都是 从数据库取数据 -> 数据操作和结构化 -> 返回给前端,在数据操作过程中需要合理地抽象, 组织、处理数据,如果选用了错误的数据结构,就会造成代码运行低效。这也是我们需要学习算法和数据结构的原因。
学习方法
这里我们用一种很原始的方法来学习算法:
- 阅读资料了解算法思想
- 纸笔模拟尝试理解
- 用自己熟悉的编程语言来实现
数据结构与类型
在往常我们的开发的的时候,经常使用的数据类型,或者我们自定义的类。都是可以理解成是一个抽象的数据类型(ADT: Abstract Data Type),它们泛指一类数据,他们有拥有共同的属性与方法。
举例:水杯
class glass:
def __init__(self,pin_pai,size,height,color):
pass
实现ADT时,我们应注意什么?
- 如何选用恰当的数据结构作为存储?
- 选取的数据结构能否满足 ADT 的功能需求
- 实现效率如何?