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.总结

不知道抛砖引玉说了那么多，是否点了重点。
其实重点是，我们要熟悉数据结构和算法的使用场合和分情况讨论。就像基础的排序算法，插入排序，数组和链表结构都可以实现，但是根据需要来选择用数组还是链表，根据需要来选择是用哪种排序方法。
很多时候，光看数据结构和算法本身，并不能加深我们对其的印象，需要联系实际中的一些情况来看，没有现成的，去发现和寻找，然后你会发现，发现和思索多了，你的思维就会跟上去了。
没有最好的，只有最适合的，有时候，我们选择了一种看似特别好的算法，可能会在某种特殊情况下性能下降很厉害，这种时候，我们就需要考虑这种特殊情况是否在我们的数据中出现的多，如果多，我们需要换一种可能不是最好，但是综合起来的性能还不错的算法。
毕竟很多时候，双刃剑就是，一个事物的优点，往往也是它的弱点，你不仅要清楚其优点所在环境，更要清楚其弱点产生的环境。这样在学习的时候会有所留意，日后用的时候也会权衡的得心应手。

给定的数据情况决定我们所采用的数据结构，具体要达成的目标和性能，决定我们采用的算法。当多种数据结构和算法可选择时，选择最合适的。也可以给不同的场景选择不同的。

以上就是我对算法入门的一些认识，深入部分尚为涉及，一点个人看算法的感受，抛砖引玉，个别深入细节，会另开章节。