为什么学数据结构和算法
最近在极客上学习了一个课程【数据结构和算法之美】，已经看了基础篇，总的来说，讲得比较通俗易懂，目前还没有代码操作，这也是后续要做的。之所以重温学习数据结构和算法，而不是去学那些新的技术架构和框架，是因为我认为数据结构、算法、设计模式、领域驱动设计DDD是技术思想和方法论之类的知识，属于道的层面的，而那些技术架构或框架（springcloud、Istio、zookeeper、Solr、RPC框架等）是建立在这些经典的技术思想和方法论之上的，属于术的层面的，而我个人比较倾向于遵循先道而后术的原则。当然，为了保持技术敏感度，我们是有必要了解那些技术架构和框架的原理和适用场景的，在需要的时候，可以想到它们，然后看看官方的技术说明文档，就能拿来用了。
或许我们在平时开发过程，也用不到太高深的数据结构和算法，但学习这些经典理论，有助于理解一些开源框架的底层原理，也是可以锻炼我们的逻辑思维。其实，我们开发中的业务逻辑也是算法，可以解决某个特定的问题，而我们学习的经典算法可以解决一系列问题。所以，熟练掌握经典算法，对我们设计和开发也是有很大帮助的。我们学习数据结构和算法，要学习它的由来，特性、适用场景及能解决的问题。
数据结构和算法归纳如下：
复杂度分析
复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。
复杂度分为时间复杂度和空间复杂度。我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，空间复杂度分析比时间复杂度分析要简单很多。空间复杂度分析是分析程序对内存的占用大小的分析，写程序的时候，内存是比较关注的性能点，若控制不好，会引起内存泄露、内存溢出、FullGC频繁的情况，而造成程序变慢、甚至崩溃的情况。
复杂度量级可分为多项式量级和非多项式量级。我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。非多项式时间复杂度的算法其实是非常低效的算法，而我们一般是多项式量级的算法问题。
其中，非多项式量级只有两个：O(2n) 和 O(n!)。
几种常见的多项式时间复杂度：
- O(1)：一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)；
- O(logn)、O(nlogn)：归并排序、快速排序；
- O(m+n)、O(m*n)：m 和 n 是表示两个数据规模。当m=n时，就是O(n)和O(n^2)。
复杂度分析方法
- 只关注循环执行次数最多的一段代码;
- 加法法则：总复杂度等于量级最大的那段代码的复杂度;
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积;
复杂度量级
复杂度分析实例
如下面的这段代码，用数学的方法分析其时间复杂度：
i=1;
while (i <= n) {
i = i * 2;
}
第三行代码是循环执行次数最多的，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。
从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。变量 i 的取值就是一个等比数列。如果把每次遍历的情况列出来，如下：
2^0 2^1 2^2 2^3 ...2^k ...2^x = n
所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过2^x =n，求解 x 。x=log2n，所以，这段代码的时间复杂度就是 O(log2n)。如果是i = i*3，也是一样的时间复杂度，只是x =log3n，但时间复杂度都是logn。
数据结构
学习了10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树;
数组、链表、栈、队列、散列表、二叉树、跳表，这几个数据结构是比较常用的，在jdk和开源框架中也出现比较多，比如红黑树在HashMap中解决哈希冲突时用到，跳表在Redis里面有用到。堆、图、Trie树用得比较少。
算法
学习了10个算法：字符串匹配算法、递归、排序或查找算法、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划。
其中，字符串匹配算法、递归、排序或查找算法、搜索、哈希算法、分治算法这些算法还是比较好理解的，也是平时用得比较多的。分治算法、贪心算法、回溯算法、动态规划更多的是一种算法思想，主要还是要结合场景去理解。
排序算法的时间复杂度、是否稳定、是否原地排序：
我的感想
课程中有句话说：“掌握了数据结构和算法，你看待问题的深度，解决问题的角度就会完全不一样”，我似乎有些同感。我认为数据结构和算法的书，还是要多看几遍，而且还要写demo代码去练习，边学边练，才会有效果。只有理论和原理学得很熟练，应用起来才能得心应手，这也是熟能生巧。看这种技术的书，不应该靠记，记是记不住多久的，而是要深入理解和思考，并联系实际应用场景。
这里先做个大概的总结，后续再根据每个数据结构和算法（上述列出的10个数据结构和10个算法），记录一些学习笔记和心得。