算法之我见(II)
5.数据结构和算法的关系
1.常见数据结构
常见的数据结构.jpg
数据结构其实逃离不了数据，数据结构发明的本身是为了更好的处理数据。其实，数据结构按照在内存里的分布总共分两类，线性和非线性。我们在非线性结构上处理数据，都是为了更好的达到我们想要的性能。
按在内存中是否是线性结构分：
- 线性结构：对应数组,下标访问O(1),排序最快O(nlogn),也有O(n).这是最直观的一个结构。
- 非线性结构：链表，树，图，其中，链表结构其实可以认为是树和图的基础结构，而图又是树结构的一个特例。
按不同的使用规则分：
- 栈，后进先出的规则，有一定顺序的，一般用线性结构实现。
- 队列，先进先出的规则，可以用线性结构实现，也可以用非线性结构实现。无论哪个结构，都需要保留两个标记，头，尾。头部负责出队列，尾部负责进队列。
- 堆，有一定规则的树结构，保证顶点是最大或者最小来称为大顶堆或者小顶堆。
- 图，抽象上比树结构多一些指向指针的结构，可以用部分线性部分非线性结构来组合表示，一般根据所需要表示图的特性来决定。
- 哈希表，这是一种线性表和链表结合的数据结构，意图在使用索引值快速的进行查找，一种用空间换时间的数据结构。
2.基本的数据结构算法
说到基础：我能想到的就两个，查找和排序。当然，不是说其他不是基础，只是我看来，这两个是很多问题的基础思路，并加以一定规律的扩展。
- 查找：
假定我们有N个线性结构的数据，我们要在N个数据中查找某个给定值。
常规的查找，我们要把整个数组走一遍，时间复杂度一般为O(N)
但是如果遇到特殊情况：
1.我们的数组是按一定规则（从小到大，从大到小，或者排好序的数组在某个节点旋转过一次且只有一次）的时候，我们可以用 二分查找 法来做，这会让平均的时间复杂度降为O(logN)
2.我们要查找的是数据中m个最大或者最小的元素，这个时候，我们可以借助堆结构。
对于非线性结构，比如说树，查找某个值，或者某几个节点的最大最小值，我们一般用动态规划或者分治（迭代实现）。
- 排序
常见排序算法的时间复杂度为O()和O(NlogN),当然也有一些高级的排序算法只要O(N)或O(N+K).例如python中给出的sort()用的是Timsort，时间复杂度为O(NlogN),兼用了二分插入排序和归并排序。
排序里的算法没有好坏，只有说在什么场合的使用。（具体排序算法，会在数据结构和算法里讲。）
其实我们想到的这两个算法是最基本的数据结构算法，高级的一些算法，能分治用动态规划的，只要找出那个基本公式使用迭代就可以解决，但是想不到的话，可能会麻烦点。寻找问题里的重复点，这是解决问题的一种思路，找意图，找到题目没有明说，但其实是存在的一种规律。这是题外话。
2.总结
不知道抛砖引玉说了那么多，是否点了重点。
其实重点是，我们要熟悉数据结构和算法的使用场合和分情况讨论。就像基础的排序算法，插入排序，数组和链表结构都可以实现，但是根据需要来选择用数组还是链表，根据需要来选择是用哪种排序方法。
很多时候，光看数据结构和算法本身，并不能加深我们对其的印象，需要联系实际中的一些情况来看，没有现成的，去发现和寻找，然后你会发现，发现和思索多了，你的思维就会跟上去了。
没有最好的，只有最适合的，有时候，我们选择了一种看似特别好的算法，可能会在某种特殊情况下性能下降很厉害，这种时候，我们就需要考虑这种特殊情况是否在我们的数据中出现的多，如果多，我们需要换一种可能不是最好，但是综合起来的性能还不错的算法。
毕竟很多时候，双刃剑就是，一个事物的优点，往往也是它的弱点，你不仅要清楚其优点所在环境，更要清楚其弱点产生的环境。这样在学习的时候会有所留意，日后用的时候也会权衡的得心应手。
给定的数据情况决定我们所采用的数据结构，具体要达成的目标和性能，决定我们采用的算法。当多种数据结构和算法可选择时，选择最合适的。也可以给不同的场景选择不同的。
以上就是我对算法入门的一些认识，深入部分尚为涉及，一点个人看算法的感受，抛砖引玉，个别深入细节，会另开章节。
