理解数据结构和算法背景数据本质算法的来源应用总结参考

背景

程序=数据结构+算法

那是现有数据结构再有算法，还是现有算法再有数据结构呢？

在我看来应该是先有数据结构，只有当有了数据，我们才会考虑算法，针对不同的数据结构会有不同的算法。

数据本质

数据的本质是什么呢？

数学上有人用集合论来推演整个近代数学，因此集合论是基础，有了最简单的数据，随着人们对数据的需求越来越多，就衍生出了各种结构和算法

算法的来源

第一个需求：如何有序的保存数据

一个简单的想法就是将数据排成一排，一个连一个，这个有序在计算机里就叫做Array

另一种方法是让数据之间指向关系，前一个指向后一个，这就叫LinkList，LinkList中用做指向关系的结构就叫做指针

第二个需求：如何判断某一个数据是否存在

对于有序的集合，我们就根据顺序一个一个找，这就叫做遍历

第三个需求：如何快速的判断某一个数据是否存在

因为集合是有序的，我们可以先看两头，然后折中不断缩减查看的范围，这就叫二分查找

另一种思路是：假设生活中我们要看下公交来没来，你可能第一次去路口看的时候，车没来，然后你回来了说车没来，但是可能车在你刚回来的时候又来了，这样子就其实是错过了车的，这种判断车来没来的方法带有很大的不确定性，对比到我们判断数是否在集合里的例子中，我们先看前面几个数据，发现没有，就认为集合里不存在我们要找的数了，这种方法就叫做贪心，而且特点也很明显就是不确定性，我们只是判断了几个数据，就认为要找的数不在集合里面了。

那有什么方法能够将贪心的不确定性变为确定性贪心呢？我们可以利用集合有序这个条件，先找中间的元素，比对大了还是小了，不断缩减搜索范围，那这个和二分查找有什么区别呢？换一个角度讲，我们在搜索或者查找的时候，就是不断在减小搜索的集合，这就是贪心。

现在还是原来的问题，怎么快速的判断某一个数据是否存在，这个如果改变底层的数据结构，那相应的算法就会变化，我们将数据组合成二叉搜索树，树的左边都比根小，右边都比根大，这种结构下搜索就非常直观了，这就是二叉查找树。

第四个需求：如何遍历一个树

在遍历树的时候我们有两个想法，一个是一条路走到底，另一个就是离的近的我们先走，对应到算法上就是深度优先和广度优先

应用

什么是动态规划

• 解空间转换
• 宽度优先
• 贪心

为什么提到上面三点呢？我们以一个例子来说明下：

有向图

我们假设有一棵树，每个节点的数值表示权重，要算出根到叶子节点的最短路径，这个怎么解呢？

首先我们需要做个转换，原先每个节点存在的是本节点的权重，现在每个节点新增根节点到本节点的最短路径，

然后算出每个中间节点的最短路径，这个过程是一个宽度优先的过程，先算第K层的最短路径，然后算K+1层的，

最后，我们在算K+1层节点的最短路径的时候，是一个贪心的过程，我们总是取K层过来的最短路径的那个节点来计算。

总结

1. 程序的本质是数据结构加算法，现有数据结构，再有算法
2. 一些复杂的算法（动态规划）其实是由一些基本的概念组合而来

• 解空间转换
• 宽度优先
• 贪心

参考

视频：硅谷之路72 理解数据结构和算法设计

blog:【硅谷之路 72】理解数据结构和算法设计