程序=数据结构+算法
那是现有数据结构再有算法,还是现有算法再有数据结构呢?
在我看来应该是先有数据结构,只有当有了数据,我们才会考虑算法,针对不同的数据结构会有不同的算法。
数据的本质是什么呢?
数学上有人用集合论来推演整个近代数学,因此集合论是基础,有了最简单的数据,随着人们对数据的需求越来越多,就衍生出了各种结构和算法
第一个需求:如何有序的保存数据
一个简单的想法就是将数据排成一排,一个连一个,这个有序在计算机里就叫做Array
另一种方法是让数据之间指向关系,前一个指向后一个,这就叫LinkList,LinkList中用做指向关系的结构就叫做指针
第二个需求:如何判断某一个数据是否存在
对于有序的集合,我们就根据顺序一个一个找,这就叫做遍历
第三个需求:如何快速的判断某一个数据是否存在
因为集合是有序的,我们可以先看两头,然后折中不断缩减查看的范围,这就叫二分查找
另一种思路是:假设生活中我们要看下公交来没来,你可能第一次去路口看的时候,车没来,然后你回来了说车没来,但是可能车在你刚回来的时候又来了,这样子就其实是错过了车的,这种判断车来没来的方法带有很大的不确定性,对比到我们判断数是否在集合里的例子中,我们先看前面几个数据,发现没有,就认为集合里不存在我们要找的数了,这种方法就叫做贪心,而且特点也很明显就是不确定性,我们只是判断了几个数据,就认为要找的数不在集合里面了。
那有什么方法能够将贪心的不确定性变为确定性贪心呢?我们可以利用集合有序这个条件,先找中间的元素,比对大了还是小了,不断缩减搜索范围,那这个和二分查找有什么区别呢?换一个角度讲,我们在搜索或者查找的时候,就是不断在减小搜索的集合,这就是贪心。
现在还是原来的问题,怎么快速的判断某一个数据是否存在,这个如果改变底层的数据结构,那相应的算法就会变化,我们将数据组合成二叉搜索树,树的左边都比根小,右边都比根大,这种结构下搜索就非常直观了,这就是二叉查找树。
第四个需求:如何遍历一个树
在遍历树的时候我们有两个想法,一个是一条路走到底,另一个就是离的近的我们先走,对应到算法上就是深度优先和广度优先
什么是动态规划
为什么提到上面三点呢?我们以一个例子来说明下:
有向图
我们假设有一棵树,每个节点的数值表示权重,要算出根到叶子节点的最短路径,这个怎么解呢?
首先我们需要做个转换,原先每个节点存在的是本节点的权重,现在每个节点新增根节点到本节点的最短路径,
然后算出每个中间节点的最短路径,这个过程是一个宽度优先的过程,先算第K层的最短路径,然后算K+1层的,
最后,我们在算K+1层节点的最短路径的时候,是一个贪心的过程,我们总是取K层过来的最短路径的那个节点来计算。