学习笔记 | 走进智能算法
©三金
刷知乎看到一个答主（知乎名：承志）在回答“编程能力主要是算法吗？”中写到：
现在市面上大多数的算法岗位，所涉及到的都是智能算法，也就是所谓的大数据算法。这类算法的特点是基于海量的数据进行统计或预测，更偏向于统计。这类问题一般来说没有最优解，只有近似解，通过优化模型和方法，可以获得更好的效果。这和ACM比赛涉及到的性能算法不太相同，性能算法是在规定的时限和空间内计算出要求的结果，并且这个结果是固定的。
答主（知乎名：Java编程指导）进一步指出，要说智能算法，首先要提到智能计算。智能计算也有人称之为“软计算”。智能算法就是人们受到自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，就这就仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计（包括设计算法），这就是智能计算的思想，包括人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。
还有一位答主总结这些算法背后的数学原理，大部分都和概率论有关。
最常用的智能算法有遗传算法、免疫算法、退火算法、粒子群算法、鱼群算法、蚁群算法和神经网络算法。
part1 必备数据结构
学习方法：不求深，但求广。
数据结构包含三个要素：逻辑结构、存储结构（物理结构）、数据的运算。
其中逻辑结构又分为线性结构（线性表、栈、队列）和非线性结构（树、图、集合）。
1、链表
采用链式存储时，逻辑上相邻的元素，物理存储位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。
2、树
二叉树的特点是每个结点之多只有两颗子树，并且二叉树的子树有左右之分，其次序不能任意颠倒，与树相似，二叉树也以递归的形式定义。
3、数组
4、复杂度分析（Big-O analysis）
part2 必刷题型
刷题路径：自己做-》参考好解法-》优化自己的解法-》不停地优化-》寻找相同题型重复练习-》总结。前期先接受自己的思考方式，暴力解法其实也是一种有效的解法。
排序与查找
1、排序（快速排序Quicksort和归并排序merge sort）
知识点
回顾下之前写的这篇文章《几种常见的排序算法》。
归并排序是分治法的一个应用。我们常把贪心算法、动态规划和分解法放在一起谈论。
1.快速排序的基本过程、时间复杂度、空间复杂度和稳定性。
2.堆排序过程，复杂度和稳定性。
3.a[0]-a[10]实现堆排序，并计算时间复杂度。
刷题总结
2、二叉搜索树（二分搜索树Binary search trees）
知识点
1.树给定前序遍历和中序遍历是否可以还原出二叉树并证明，如果给定前序和后序呢？
刷题总结
3、哈希表（Hash tables）
知识点
哈希表又称为散列表，是根据关键字码的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加速查找速度，其中映射函数叫做散列函数，存放记录的数组叫做散列表。
hash_map基于hash table（哈希表）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。它以键和值组成的对为基础。
统计字符在字符串出现的次数，或是否在某字符串中出现等等这类问题可以用哈希表来处理。当字符是8位时，可以建立一个长度为256的哈希表（形式是数组），数组的下标是字符对应的ASCII码，数组的值可以是出现的次数，或者是否出现的布尔型变量。[1]
刷题总结
4、二维数组（2D arrays）
二维数组行地址、列地址。
part3 必学机器学习算法
学习方法：掌握机器学习的算法的具体原理，最好手动推导这些算法的数学部分，而不是走马观花地看一遍。
001 监督学习
1、线性回归（Linear Regression）❤️
2、逻辑回归（Logistic Regression）❤️
Logistic回归的损失函数和梯度分别是多少
3、支持向量机（Support Vector Machine，SVM）
SVM的数学推导
4、朴素贝叶斯（Naive Bayes）❤️
5、最近邻居/k-近邻算法（K-Nearest Neighbors，KNN）
6、EM❤️
7、降维（Dimensional Reduction）
8、梯度增加（Gradient Boosting）
9、决策树（Decision Tree）
10、k-平均（K-Means）
11、随机森林（Random Forest）
002 非监督学习
1、主成分分析❤️
2、聚类分析
3、关联规则学习
4、马尔可夫链蒙特卡洛法❤️
003 最优化
1、梯度下降法❤️
2、牛顿法
3、动态规划（Dynamic programming）
part4 概率论小题
学习方法：不需要很强的计算能力，但需要很深的功底。前提是要理解，而不是死记硬背。
1、如何生成概率为pi/4的事件？
2.事件和随机变量(random variables)之间相互独立(mutually independent)和两两独立(pairwise independent)分别是什么意思？
3.在圆周上随机抽取3个点，问圆心包含在他们构成的三角形内的概率是多少？如何写一个程序来验证你的结果？
4.给定一个未知概率的不均匀硬币，即一个能够生成X∼Ber(p)未知的随机数生成器，如果生成一个0,1,2,…,M−1之间的随机数。假设随机数生成器是一个函数f，试写一个程序来生成需要的随机数。平均对f的调用次数／投掷硬币的次数是多少？可以如何优化？如果检验结果是否足够随机？
5.给定一个均匀硬币，如果构造一个概率为p的伯努利变量？其中p已知但不一定是有理数(rational number)。若均匀硬币生成器是一个函数f是一个传入的参数，写一个程序来生成X∼Ber(p)。
6.我国的驾照科目一考试的题库为1000题，你下载了一个手机App可以进行模拟考试。每次模拟考试会从这1000题中随机选出100道不重复的题。如果你进行了10次模拟考试，那么你见到过的题库中的题目数量的期望值为多少? 写一个程序验证这个结论。
参考资料：
1.《统计学习方法》 李航
2.公众号：编程员宝藏。特别感谢这个公众号，参考了它【计算机考研复试面试】内容，归纳总结一级棒！
-
版权声明：本文为CSDN博主「melody96313」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/melody96313/java/article/details/79721072 ↩
