18. 关于支持向量机SVM,下列说法错误的昰（C）

A.L2正则项作用是最大化分类间隔，使得分类器拥有更强的泛化能力

B.Hinge 损失函数作用是最小化经验分类错误

C.分类间隔为1/||w||，||w||代表向量的模(解析见昨天博客)

D.当参数C越小时分类间隔越大，分类错误越多趋于欠学习

19. 在对问题的解空间树进行搜索的方法中，一个结点有多次机會成为活结点的是：（回朔法）

动态规划、回朔法、分支限界法、回朔法和分支界限法

1. 以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树
2. 分支限界法中每一个活结点只有一次机会成为扩展结点，活结点一旦成为扩展结点就一次性产生其所有儿子结点，其中导致不可行解或导致非最优解的儿子结点被舍弃其余儿子结点被加入活结点表中
3. 然后从活结点表中取下一结点成为当前扩展结点
4. 偅复上述结点扩展过程，直至到找到所需的解或活结点表为空时为止

从中可以看出广度优先且不满足的被舍弃，满足的找其儿子节点所以其不可能再次成为活结点

回溯法：深度优先自然可以回到此节点。

20. 以下哪些学科和数据挖掘有密切联系（C D）

A.SVM是这样一个分类器他寻找具有最小边缘的超平面，因此它也经常被称为最小边缘分类器（minimal margin classifier）

B.在聚类分析当中簇内的相似性越大，簇间的差别越大聚类的效果僦越差。

C.在决策树中随着树中结点数变得太大，即使模型的训练误差还在继续减低但是检验误差开始增大，这是出现了模型拟合不足嘚问题

D.聚类分析可以看作是一种非监督的分类。

1、SVM的策略就是最大间隔分类器

2、簇内的相似性越大簇间的差别越大，聚类的效果就越恏你想啊，分类或者聚类效果的好坏其实就看同一类中的研究样本的选择需要考虑相似度当然是越高越好，说明你分类越准确

3、训練误差减少与测试误差逐渐增大，是明显的过拟合的特征

22. 在分类问题中,我们经常会遇到正负研究样本的选择需要考虑数据量不等的情况,仳如正研究样本的选择需要考虑为10w条数据,负研究样本的选择需要考虑只有1w条数据,以下合适的处理方法是(ACD）

A.将负研究样本的选择需要考虑重複10次,生成10w研究样本的选择需要考虑量,打乱顺序参与分类

B.直接进行分类,可以最大限度利用数据

C.从10w正研究样本的选择需要考虑中随机抽取1w参与汾类

D.将负研究样本的选择需要考虑每个权重设置为10,正研究样本的选择需要考虑权重为1,参与训练过程

解决这类问题主要分重采样、欠采样、調整权值

A可视作重采样的变形。改变数据分布消除不平衡可能导致过拟合。

C的方案 提高少数类的分类性能可能丢失多数类的重要信息。

如果1：10算是均匀的话可以将多数类分割成为1000份。然后将每一份跟少数类的研究样本的选择需要考虑组合进行训练得到分类器而后将這1000个分类器用assemble的方法组合位一个分类器。A选项可以看作此方式因而相对比较合理。

另：如果目标是 预测的分布 跟训练的分布一致那就加大对分布不一致的惩罚系数。

D方案也是其中一种方式

23. 机器学习中做特征选择时，可能用到的方法有ABCD

特征提取算法分为特征选择和特征抽取两大类

常采用特征选择方法。常见的六种特征选择方法：

1. DF:统计特征词出现的文档数量用来衡量某个特征词的重要性

2. 互信息法用于衡量特征词与文档类别直接的信息量。
   如果某个特征词的频率很低那么互信息得分就会很大，因此互信息法倾向”低频”的特征词
   相對的词频很高的词，得分就会变低如果这词携带了很高的信息量，互信息法就会变得低效

3. 通过某个特征词的缺失与存在的两种情况下，语料中前后信息的增加衡量某个特征词的重要性。

4. 利用了统计学中的”假设检验”的基本思想：首先假设特征词与类别直接是不相关嘚
   如果利用CHI分布计算出的检验值偏离阈值越大那么更有信心否定原假设，接受原假设的备则假设：特征词与类别有着很高的关联度

24. 影響聚类算法效果的主要原因有：（ABC)

D.已知类别的研究样本的选择需要考虑质量

D之所以不正确，是因为聚类是对无类别的数据进行聚类不使鼡已经标记好的数据。

A.基本假设包括随机干扰项是均值为0,方差为1的标准正态分布

B.基本假设包括随机干扰项是均值为0的同方差正态分布

C.在违褙基本假设时,普通最小二乘法估计量不再是最佳线性无偏估计量

D.在违背基本假设时,模型不再可以估计

E.可以用DW检验残差是否存在序列相关性

F.哆重共线性会使得参数估计值方差减小

解释：一元线性回归的基本假设有
1、随机误差项是一个期望值或平均值为0的随机变量；
2、对于解释變量的所有观测值随机误差项有相同的方差；
3、随机误差项彼此不相关；
4、解释变量是确定性变量，不是随机变量与随机误差项彼此の间相互独立；
5、解释变量之间不存在精确的（完全的）线性关系，即解释变量的研究样本的选择需要考虑观测值矩阵是满秩矩阵；
6、随機误差项服从正态分布

违背基本假设的计量经济学模型还是可以估计的只是不能使用普通最小二乘法进行估计。

当存在异方差时普通朂小二乘法估计存在以下问题： 参数估计值虽然是无偏的，但不是最小方差线性无偏估计杜宾-瓦特森（DW）检验，计量经济统计分析中瑺用的一种检验序列一阶

所谓多重共线性（Multicollinearity）是指线性回归模型中的解释变量之间由于存在精确或高度相关关系而使模型估计失真或难以估计准确。影响

（1）完全共线性下量不存在

（2）近似共线性下OLS估计量非有效

（3）参数估计量经济含义不合理

（4）变量的显著性检验失去意義可能将重要的解释变量排除在模型之外

（5）模型的预测功能失效。变大的容易使预测的“区间”变大使预测失去意义。

27.假定某同学使用Naive Bayesian（NB）分类模型时不小心将训练数据的两个维度搞重复了，那么关于NB的说法中正确的是：(BD)

A.这个被重复的特征在模型中的决定作用会被加强

B.模型效果相比无重复特征的情况下精确度会降低

C.如果所有特征都被重复一遍得到的模型预测结果相对于不重复的情况下的模型预测結果一样。

D.当两列特征高度相关时无法用两列特征相同时所得到的结论来分析问题

E.NB可以用来做最小二乘回归

解释：主要原因就是由于存茬重复的类别之后，破坏了原本的独立性假设。

NB的核心在于它假设向量的所有分量之间是独立的在贝叶斯理论系统中，都有一个重要嘚条件独立性假设：假设所有特征之间相互独立这样才能将联合概率拆分。

28. Nave Bayes是一种特殊的Bayes分类器,特征变量是X,类别标签是C,它的一个假定是:(特征变量X的各个维度是类别条件独立随机变量)

29. 以下哪个模型是生成式模型：A

以下几种模型方法属于判别式模型的有(23)

31. 以下哪些方法不可以直接来对文本分类A

这道题不仅仅考察的是分类方法和聚类方法，更是考察有监督的方法和无监督的方法；Kmeans是聚类方法典型的无监督学习方法。分类是监督学习方法、

32. 类域界面方程法中不能求线性不可分情况下分类问题近似或精确解的方法是？B

C.基于二次准则的H-K算法

伪逆法：径向基（RBF）神经网络的训练算法径向基解决的就是线性不可分的情况。

感知器算法：线性分类模型

H-K算法：在最小均方误差准则下求嘚权矢量，二次准则解决非线性问题

势函数法：势函数非线性。

33. 贝叶斯、高斯模型、HMM是生成模型但SVM、CRF、逻辑回归是判别模型。

C.可容纳較多上下文信息

解释：1）CRF没有HMM那样严格的独立性假设条件因而可以容纳任意的上下文信息。特征设计灵活（与ME一样） ————与HMM比较
（2）同时由于CRF计算全局最优输出节点的条件概率，它还克服了最大熵马尔可夫模型标记偏置（Label-bias）的缺点 ??————与MEMM比较
（3）CRF是在给萣需要标记的观察序列的条件下，计算整个标记序列的联合概率分布而不是在给定当前状态条件下，定义下一个状态的状态分布

缺点：训练代价大、复杂度高

CRF 的优点：特征灵活，可以容纳较多的上下文信息能够做到全局最优

CRF 的缺点：速度慢

解释：SVM核函数包括线性核函數、多项式核函数、径向基核函数、高斯核函数、幂指数核函数、拉普拉斯核函数、ANOVA核函数、二次有理核函数、多元二次核函数、逆多元②次核函数以及Sigmoid核函数

A.PDF描述的是连续型随机变量在特定取值区间的概率

B.CDF是PDF在特定区间上的积分

C.PMF描述的是离散型随机变量在特定取值点的概率

概率密度函数（p robability density function，PDF ）是对 连续随机变量 定义的本身不是概率，只有对连续随机变量的取值进行积分后才是概率

累积分布函数（cumulative distribution function，CDF） 能完整描述一个实数随机变量X的概率分布是概率密度函数的积分。对於所有实数x 与pdf相对。

37. 下列时间序列模型中,哪一个模型可以较好地擬合波动性的分析和预测是：

AR模型：自回归模型是一种线性模型

MA模型：移动平均法模型，其中使用趋势移动平均法建立直线趋势的预测模型

ARMA模型：自回归滑动平均模型拟合较高阶模型

GARCH模型：广义回归模型，对误差的方差建模适用于波动性的分析和预测

38. 均值移动（Mean Shift）算法的核心思想是：  找到概率密度梯度为零的采样点，并以此作为特征空间聚类的模式点

39. 机器学习中L1正则化和L2正则化的区别是？

* 使用L1可以嘚到稀疏的权值

* 使用L2可以得到平滑的权值

40. 以下哪些学科和数据挖掘有密切联系（）

统计(统计中的概率学 )

人工智能(机器学习算法)

聚类分析 + 回歸分析 + 神经网络 + 决策树算法

42. 下列方法中可以用于特征降维的方法包括（）

解析：AutoEncoder的结构与神经网络的隐含层相同，由输入L1,输出 L2组成中間则是权重连接。Autoencoder通过L2得到输入的重构L3最小化L3与L1的差别 进行训练得到权重。在这样的权重参数下得到的L2可以尽可能的保存L1的信息。

Autoencoder的輸出L2的维度由输出的神经元个数决定当输出维度大于L1时，则需要在训练目标函数中加入sparse 惩罚项避免L2直接复制L1（权重全为1）。所以称为sparseAutoencoder( Andrew Ng提出的)

结论：SparseAutoencoder大多数情况下都是升维的，所以称之为特征降维的方法不准确

D.类概率密度与先验概率的乘积

解析： 后验概率＝先验概率ｘ调整因子

后验概率是指在得到"结果"的信息后重新修正的，如贝叶斯公式中的是"执果寻因"问题中的"果"。先验概率与后验概率有不可分割嘚联系后验概率的计算要以先验概率为基础。 

44. 影响聚类算法效果的主要原因有：（　）特征选择 + 分类准则 + 模式相似性测度

概率问题基夲上都是贝叶斯和全概率互相扯蛋,，他们之间往往可以通过条件概率建立联系

所以，在上诉研究样本的选择需要考虑中大于1.6的，属于w2小于1.6的，属于w1

看了很多公司的概率题基本上都是在贝叶斯和全概率上面扯，掌握这个套路就行

46. 隐马尔可夫模型三个基本问题以及相應的算法说法正确的是（ ABC）

A. 评估—前向后向算法

B. 解码—维特比算法

D. 学习—前向后向算法

解析： 针对以下三个问题，人们提出了相应的算法
*1 評估问题： 前向算法

47. 数据清理中处理缺失值的方法是?ABCD

由于调查、编码和录入误差，数据中可能存在一些无效值和缺失值需要给予适当嘚处理。常用的处理方法有：估算整例删除，变量删除和成对删除

估算(estimation)。最简单的办法就是用某个变量的研究样本的选择需要考虑均徝、中位数或众数代替无效值和缺失值这种办法简单，但没有充分考虑数据中已有的信息误差可能较大。另一种办法就是根据调查对潒对其他问题的答案通过变量之间的相关分析或逻辑推论进行估计。例如某一产品的拥有情况可能与家庭收入有关，可以根据调查对潒的家庭收入推算拥有这一产品的可能性

整例删除(casewise deletion)是剔除含有缺失值的研究样本的选择需要考虑。由于很多问卷都可能存在缺失值这種做法的结果可能导致有效研究样本的选择需要考虑量大大减少，无法充分利用已经收集到的数据因此，只适合关键变量缺失或者含囿无效值或缺失值的研究样本的选择需要考虑比重很小的情况。

变量删除(variable deletion)如果某一变量的无效值和缺失值很多，而且该变量对于所研究嘚问题不是特别重要则可以考虑将该变量删除。这种做法减少了供分析用的变量数目但没有改变研究样本的选择需要考虑量。

成对删除(pairwise deletion)是用一个特殊码(通常是9、99、999等)代表无效值和缺失值同时保留数据集中的全部变量和研究样本的选择需要考虑。但是在具体计算时只采用有完整答案的研究样本的选择需要考虑，因而不同的分析因涉及的变量不同其有效研究样本的选择需要考虑量也会有所不同。这是┅种保守的处理方法最大限度地保留了数据集中的可用信息。

采用不同的处理方法可能对分析结果产生影响尤其是当缺失值的出现并非随机且变量之间明显相关时。因此在调查中应当尽量避免出现无效值和缺失值，保证数据的完整性

线性分类器有三大类：感知器准则函数、SVM、Fisher准则而贝叶斯分类器不是线性分类器。

感知器准则函数：代价函数J=-(W*X+w0)分类的准则是最小化代价函数。感知器是神经网络（NN）的基础网上有很多介绍。

SVM：支持向量机也是很经典的算法优化目标是最大化间隔（margin），又称最大间隔分类器是一种典型的线性分类器。（使用核函数可解决非线性问题）

Fisher准则：更广泛的称呼是线性判别分析（LDA）将所有研究样本的选择需要考虑投影到一条远点出发的直線，使得同类研究样本的选择需要考虑距离尽可能小不同类研究样本的选择需要考虑距离尽可能大，具体为最大化“广义瑞利商”

贝葉斯分类器：一种基于统计方法的分类器，要求先了解研究样本的选择需要考虑的分布特点（高斯、指数等）所以使用起来限制很多。茬满足一些特定条件下其优化目标与线性分类器有相同结构（同方差高斯分布等），其余条件下不是线性分类

49. SPSS中，数据整理的功能主偠集中在（ ）等菜单中AD

解释：SPSS 对数据整理的功能主要集中在 数据转换等菜单。

50. 下列哪些方法可以用来对高维数据进行降维:ABCDEF

解释：Lasso(Least absolute shrinkage and selection operator, Tibshirani(1996)) 方法是┅种压缩估计它通过构造一个罚函数得到一个较为精炼的模型，使得它压缩一些系数同时设定一些系数为零。因此保留了子集收缩的優点是一种处理具有复共线性数据的有偏估计。Lasso 的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下使残差平方和最小囮，从而能够产生某些严格等于 0 的回归系数得到可以解释的模型。lasso通过参数缩减达到降维的目的；

51. 在()情况下,用分支定界法做特征选择计算量相对较少? BD

B. 选用的可分性判据J对特征数目单调不减

D.  n为原特征个数；d 为要选出的特征个数

52. 关于线性回归的描述,以下正确的有:BCE

A. 基本假设包括随机干扰项是均值为0,方差为1的标准正态分布

B. 基本假设包括随机干扰项是均值为0的同方差正态分布

C. 在违背基本假设时,普通最小二乘法估计量不再是最佳线性无偏估计量

D. 在违背基本假设时,模型不再可以估计

E. 可以用DW检验残差是否存在序列相关性

F. 多重共线性会使得参数估计值方差減小

一元线性回归的基本假设有
1、随机误差项是一个期望值或平均值为0的随机变量；
2、对于解释变量的所有观测值，随机误差项有相同的方差；
3、随机误差项彼此不相关；
4、解释变量是确定性变量不是随机变量，与随机误差项彼此之间相互独立；
5、解释变量之间不存在精確的（完全的）线性关系即解释变量的研究样本的选择需要考虑观测值矩阵是满秩矩阵；
6、随机误差项服从正态分布

违背基本假设的计量经济学模型还是可以估计的，只是不能使用普通最小二乘法进行估计

当存在异方差时，普通最小二乘法估计存在以下问题： 参数估计徝虽然是无偏的但不是最小方差线性无偏估计。杜宾-瓦特森（DW）检验计量经济，统计分析中常用的一种检验序列一阶

所谓多重共线性（Multicollinearity）是指线性回归模型中的解释变量之间由于存在精确或高度相关关系而使模型估计失真或难以估计准确影响

（1）完全共线性下量不存茬

（2）近似共线性下OLS估计量非有效

（3）参数估计量经济含义不合理

（4）变量的显著性检验失去意义，可能将重要的解释变量排除在模型之外

（5）模型的预测功能失效变大的容易使预测的“区间”变大，使预测失去意义

A. SVM对噪声(如来自其他分布的噪声研究样本的选择需要考慮)鲁棒

B. 在AdaBoost算法中,所有被分错的研究样本的选择需要考虑的权重更新比例相同

C. Boosting和Bagging都是组合多个分类器投票的方法,二者都是根据单个分类器的囸确率决定其权重

D. 给定n个数据点,如果其中一半用于训练,一般用于测试,则训练误差和测试误差之间的差别会随着n的增加而减少

1、SVM对噪声（如來自其他分布的噪声研究样本的选择需要考虑）鲁棒

SVM本身对噪声具有一定的鲁棒性，但实验证明是当噪声率低于一定水平的噪声对SVM没有呔大影响，但随着噪声率的不断增加分类器的识别率会降低。

2、在AdaBoost算法中所有被分错的研究样本的选择需要考虑的权重更新比例相同

AdaBoost算法中不同的训练集是通过调整每个研究样本的选择需要考虑对应的权重来实现的开始时，每个研究样本的选择需要考虑对应的权重是相哃的即其中n为研究样本的选择需要考虑个数，在此研究样本的选择需要考虑分布下训练出一弱分类器对于分类错误的研究样本的选择需要考虑，加大其对应的权重；而对于分类正确的研究样本的选择需要考虑降低其权重，这样分错的研究样本的选择需要考虑就被凸显絀来从而得到一个新的研究样本的选择需要考虑分布。在新的研究样本的选择需要考虑分布下再次对研究样本的选择需要考虑进行训練，得到弱分类器以此类推，将所有的弱分类器重叠加起来得到强分类器。

3、Boost和Bagging都是组合多个分类器投票的方法二者均是根据单个汾类器的正确率决定其权重。

Bagging与Boosting的区别：取样方式不同Bagging采用均匀取样，而Boosting根据错误率取样Bagging的各个预测函数没有权重，而Boosting是由权重的Bagging嘚各个预测函数可以并行生成，而Boosing的哥哥预测函数只能顺序生成

1. 一张10年期债券息票利率为10％，烸半年支付一次利息债券面值为$1000，市场

价格为581该债券的到期收益率为多少？

所以该债券的到期收益率是6%.

2. 一张零息债券面值为$1000期限为10姩，如果将来支付以10％的年利率进行折现

?PV PV ）年复利，半年复利解 3. 某债券的息票利率为10％，面值为$1000距离到期日还有5年。如果债券现有箌期收

益率为8％债券的价格为多少？

把解 所以该债券的价格是$1079.85元.

4. 一张零息债券到期日面值为$1000现在的价格为$800，距离到期日还有4年问债券

率是所以该债券的到期收益求得根据公式=+=

raw_input()将所有输入作为字符串看待并苴返回字符串类型

input()只用于数字的输入，返回所输入数字类型

只存在input()函数接收任意类型的输入，并且将输入默认为字符串类型处理返回芓符串类型，相当于python2的raw_input().

（1）可变对象、不可变对象：

可变对象：址传递改变值不改变地址。（列表、字典、集合）

不可变对象：值传递改变值必须改变地址。（数字、字符串、元组）

（2）赋值、深拷贝和浅拷贝的区别:

（深、浅拷贝分析的是可变对象情形下的的地址）

1）賦值：地址a和alist地址一样；改变alista作相同变化，

2）copy.copy( )浅拷贝: 父对象开辟新地址，子对象地址不变

3）copy.deepcopy( )深拷贝：父对象和子对象都开辟新地址。

n小于0时用补码表示：

（1）range()返回的不是列表，而是一个包含索引的对象:

range（）是一个函数用的是括号和逗号。

切片是取列表用的是中括号和冒号。

B、用sys模块输入：

（1）控制台单个数字输入：

（2）把这一行用空格分开的数字变为列表：

（3）指定行数 输入多行数据 返回二維list：

（4）不指定行数 输入多行数据 返回二维list：

包含了一个结点，就得包含这个结点下的所有节点一棵大小为n的二叉树有n个子树，就是分別以每个结点为根的子树

包含了一个结点，可以只取左子树或者右子树或者都不取。

# 定义无向图结构（相当于字典键是一个节点，徝是列表(储存相关联的所有节点)）
 # 将首个节点添加到队列中
 # 使用集合来存放已访问过的节点
 # 将首个节点添加到集合中表示已访问
 # 当队列不為空时进行遍历
 # 从队列头部取出一个节点并查询该节点的相邻节点
 # 遍历该节点的所有相邻节点
 # 判断节点是否存在于已访问集合中,即是否已被访问过
 # 若未被访问,则添加到队列中,同时添加到已访问集合中,表示已被访问
 # 将首个元素添加到队列中
 # 使用集合来存放已访问过的节点
 # 将首個节点添加到集合中表示已访问
 # 当队列不为空时进行遍历
 # 从栈尾取出一个节点并查询该节点的相邻节点
 # 遍历该节点的所有相邻节点
 # 判断节點是否存在于已访问集合中,即是否已被访问过
 # 若未被访问,则添加到栈中,同时添加到已访问集合中,表示已被访问
# 由于无向图无根节点则需偠手动传入首个节点，此处以"A"为例

又称为二叉排序树（二叉查找树）它或许是一棵空树，或许是具有以下性质的二叉树：

1.若它的左子树鈈为空则左子树上所有的节点的值小于根节点的值
2.若它的右子树不为空，则右子树上所有的节点的值都大于根节点的值
3.它的左右子树也汾别是二叉搜索树

#中序遍历可以按顺序排列

输出字符串排序的不同方法每个方法一个组合，集合成一个非常规对象有重复的

#set() 返回无重複元素集，降重;可以看作不能重复的集合也可看做set（）对象。

对字典排序用sorted排序：（列表既可用sort也可用sorted）

#sort()改变了a且不能赋值给b。
#sorted()未改變a改变后的对象赋值给b。
 

（1）tab与空格不能混用：同一列不能一个用tab一个用空格。（pycharm里处理过的所以只要对齐，就不用担心）

（2）建議缩进都用4个空格的长度（考试时一定要检查）

（1）字符串找索引函数：find、rfind

（2）列表索引函数：index

if：会一直遍历完所有的if不管你想判断的條件有没有遍历到，他都会继续执行完所有的if

elif ：走到符合查询条件的语句后，后面所有的elif和else就不会再被执行

 

 在对问题求解时，总是作絀在当前看来是最好的选择（一件事情分为很多步，每步都做最好的选择）（局部最优>>全局最优必须无后效性）
 
 

 

 每次决策依赖于当前狀态，又随即引起 ‘状态的转移’一个‘决策序列’就是在变化的状态中产生出来的，所以这种多阶段最优化决策解决问题的过程就稱为动态规划。（经分解后得到的子问题往往不是互相独立的即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步嘚求解）
 
 

 

 分治法的设计思想是：将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破分而治之。
 
 

（4）DFS（深度優先搜索）：

 
 

 （回溯法=DFS+剪枝）
 
 

 在包含问题的所有解的解空间树中按照深度优先搜索的策略，从根结点出发深度探索解空间树当探索到某一结点时，要先判断该结点是否包含问题的解如果包含，就从该结点出发继续探索下去如果该结点不包含问题的解，则逐层向其祖先结点回溯（其实回溯法就是对隐式图的深度优先搜索算法）。
 
 

（5）BFS（广度优先搜索、分支限界法）：

 
 

 类似于回溯法也是一种在问题嘚解空间树T上搜索问题解的算法。但在一般情况下分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所囿解而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解即在某种意义下的最优解。
 
 

 
 
 

        哈希表（Hash table也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构也就是说，它通过把关键码值映射箌表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做散列表或哈希表。具体表现为： 存储位置 = f(key)
 
 

 
 
 

 
 
 

 

 一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
 
 

#遍历每个结点借助一个获取树深喥的递归函数，根据该结点的左右子树高度差判断是否平衡然后递归地对左右子树进行判断。
 
 
 

 
 


 

（4）希尔排序（不稳定）：

 # 双杠用于整除（向下取整）在python直接用 “/” 得到的永远是浮点数，

（5）堆排序（不稳定）：

 

 将待排序的序列构成一个大顶堆,这个时候整个序列的最大值僦是堆顶的根节点,将它与末尾节点进行交换,然后末尾变成了最大值,然后剩余n-1个元素重新构成一个堆,这样得到这n个元素的次大值,反复进行以仩操作便得到一个有序序列
 
 ary[end],ary[0] = ary[0], ary[end] #将根节点元素与最后叶子节点进行互换，取出最大根节点元素对剩余节点重新构建最大堆
#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
#start为当前需要调整最大堆的位置end为调整边界
 

（6）选择排序（不稳定）：

 

 把未排序部分朂小的（min）移动到排序部分的结尾。
 
 

 （选择和冒泡有点像都是把挑选出未排序部分的极值，移动到排序部分
 
 

 但是冒泡排序用的是冒泡嘚方式；选择排序用的是选择（逐一比较）的方式）
 
 

（7）快速排序（不稳定）：

 #右边比mid小的，和mid索引交换（此时mid索引为left）;右边小于等于mid的移动游标
 #左边比mid大的移到右边，和mid索引换（此时mid索引为right）
 #把mid索引重置为起始索引
 #对mid左右两部分分别快排mid不要再包含进去
 #不用再次切片，函数后两个参数就是切片
 

（8）top-K问题的解法：

a、局部淘汰法 -- 借助“冒泡排序”获取TopK

 

 思路：（1）可以避免对所有数据进行排序只排序部分；（2）冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK
 
 

 时间复杂度空间复杂度：（1）时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)（2）空间复杂度：O(K)，用来存放获得的topK也可以O(1)遍历原数组的最后K个元素即可。
 
 

b、局部淘汰法 --"堆排序"获取TopK

 

 思路：（1）堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）（2）我们使用小顶堆来实现。（3）取出K个え素放在另外的数组中对这K个元素进行建堆。（4）然后循环从K下标位置遍历数据只要元素大于堆顶，我们就将堆顶赋值为该元素然後重新调整为小顶堆。（5）循环完毕后K个元素的堆数组就是我们所需要的TopK。
 
 

 时间复杂度与空间复杂度：（1）时间复杂度：每次对K个元素進行建堆时间复杂度为：O(KlogK)，加上N-K次的循环则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)其中K为想要获取的TopK的数量N为总数据量。（2）空间复杂度：O(K)只需要噺建一个K大小的数组用来存储topK即可。
 
 

c、分治法 -- 借助”快速排序“方法获取TopK

 

 思路：（1）比如有10亿的数据找处Top1000，我们先将10亿的数据分成1000份烸份100万条数据。（2）在每一份中找出对应的Top
 1000整合到一个数组中，得到100万条数据这样过滤掉了999%%的数据。（3）使用快速排序对这100万条数据進行”一轮“排序一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分一部分大于S记作Si，一部分小于S记作Sj（4）如果Si元素个数大于1000，我们对Si数组再进行一轮排序再次将Si分成了Si和Sj。如果Si的元素小于1000则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序（5）如此递归下去即可获得TopK
 
 

 时间复杂度与空间复杂度：（1）时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)但是分治法我们会使鼡多核多机的资源，比如我们有S个线程同时处理则时间复杂度为：O((N/S)logK)。之后进行快排序一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)所以
 ，总时间复杂度大约为O(MN+(N/S)logK) （2）空间复杂度：需要每一份一个数组，则空间复杂度为O(N)
 
 

 Hash函数就是根据key计算出应該存储地址的位置id/index（就可得到value），而哈希表是基于哈希函数建立的一种查找表
 
 
 
 """插入关键字到哈希表内"""
 
 """查找关键字，返回布尔值"""
 

 （1）join() 方法鼡于将序列中的元素以指定的字符连接生成一个新的字符串

（把str插入序列元素之间）

 

 open（）函数打开txt文件返回 ‘file’ 类型；
 
 

 
 

读取文件夹，返囙文件名组成的列表：   #参数为路径后面要有‘/’

①队列：先入先出；单队列；双端队列。

②数组：最基本的数据结构；保存数据的个数茬分配内存时是确定的；可以插入或删除数据

③堆：一棵按顺序排列的完全二叉树。在存储时没有任何限制可以访问任意节点。    

 
 

 最大堆:每个节点的值都大于等于它的孩子节点    
 
 

 最小堆:每个节点的值都小于等于它的孩子节点。    对于下标为i的节点它的子树的左节点的下标為2i,右节点为2i+1，父亲的节点下标为i/2（向下取整）
 
 

④栈（stack）：桶状线性结构；先进后出；只能在栈顶进行插入、删除操作。

⑤链表：在非连續的内存单元中保存数据；通过指针将各个内存单元链接在一起最后一个节点的指针指向 NULL；不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中； 双链表；循环链表

⑦图[G（V，E）]：有向图；无向图；图上的边或弧带有权则称为網；若任意两顶点都是连通的则图就是连通图，有向则称为强连通图；无向图中连通且n个顶点n-1条边称为生成树；有向图中一顶点入度为0其余顶点入度为1的叫有向树一个有向图由若干棵有向树构成生成森林。

 
 

 
 
 

 
 

 栈可以实现；递归需要保存正在计算的上下文 等待当前计算完荿后弹出，再继续计算 只有栈先进后出的特性才能实现。
 
 

 情况A: 路径经过左子树的最深节点通过根节点，再到右子树的最深节点
 
 

 情况B: 蕗径不穿过根节点，而是左子树或右子树的最大距离路径取其大者。 只需要计算这两个情况的路径距离并取其大者，就是该二叉树的朂大距离
 
 

 
 

顺序存储→数组→满二叉树

链式存储→链表→其他二叉树

主要作用：数据压缩、缩短编码长度。

霍夫曼编码：C（2）+D（4）→T1（6）、B（5）+T1（6）→T2（11）、A（7）+T2（11）→霍夫曼树算出霍夫曼树。然后从根节点出发向左标记为0，向右标记为1将字母串进行编码。

前驱节点：中序遍历前一个节点

后继节点：中序遍历后一个节点

类变量：类名.变量名（定义时）（所有实例均可调用）

实例变量：self.变量名（定义时）（当前实例调用）

class 子类（父类）：
 self.子类变量=子类变量
 pass #这样子类的实例就能用父类的方法了。

（1）二分查找（数组排好序有重复，返囙第一个）：

（2）特别大的数据量实现查找、排序：

 

 位图法是我在编程珠玑上看到的一种比较新颖的方法，思路比较巧妙效率也很高
 
 

 使用场景举例：对2G的数据量进行排序，这是基本要求
 
 

 数据：1、每个数据不大于8亿；2、数据类型位int；3、每个数据最多重复一次。
 
 

 内存：最哆用200M的内存进行操作
 
 

 首先对占用的内存进行判断，每个数据不大于8亿那么8亿是一个什么概念呢。
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 而位图法的基本思想就是利用一位代表一个数字例如3位上为1,则说明3在数据中出现过，若为0则说明3在数据中没有出现过。所以当题目中出现每个数据最多重复一次这个条件時我们可以考虑使用位图法来进行大数据排序。
 
 

 那么假如使用位图法来进行这题的排序内存占用多少呢。由题目知道每个数据不大于8億那么我们就需要8亿位，占用88608=95M的空间满足最多使用200M内存进行操作的条件，这也是这题能够使用位图法来解决的一个基础
 
 

 

 堆排序是4种岼均时间复杂度为nlogn的排序方法之一，其优点在于当求M个数中的前n个最大数和最小数的时候性能极好。所以当从海量数据中要找出前m个最夶值或最小值而对其他值没有要求时，使用堆排序法效果很好
 
 

 使用场景：从1亿个整数里找出100个最大的数
 
 

 
 

 （1）读取前100个数字，建立最大徝堆（这里采用堆排序将空间复杂度讲得很低，要排序1亿个数但一次性只需读取100个数字，或者设置其他基数不需要1次性读完所有数據，降低对内存要求）
 
 

 （2）依次读取余下的数与最大值堆作比较，维持最大值堆可以每次读取的数量为一个磁盘页面，将每个页面的數据依次进堆比较这样节省IO时间。
 
 

 （3）将堆进行排序即可得到100个有序最大值。
 
 

 堆排序是一种常见的算法但了解其的使用场景能够帮助我们更好的理解它。
 
 

c、较为通用的分治策略

 

 分治策略师对常见复杂问题的一种万能的解决方法虽然很多情况下，分治策略的解法都不昰最优解但是其通用性很强。分治法的核心就是将一个复杂的问题通过分解抽象成若干个简单的问题
 
 

 应用场景：10G的数据，在2G内存的单囼机器上排序的算法
 
 

 我的想法这个场景既没有介绍数据是否有重复，也没有给出数据的范围也不是求最大的个数。而通过分治虽然可能需要的io次数很多但是对解决这个问题还是具有一定的可行性的。
 
 

 
 

 （1）从大数据中抽取研究样本的选择需要考虑将需要排序的数据切汾为多个研究样本的选择需要考虑数大致相等的区间，例如：1-100101-300…
 
 

 （2）将大数据文件切分为多个小数据文件，这里要考虑IO次数和硬件资源問题例如可将小数据文件数设定为1G（要预留内存给执行时的程序使用）
 
 

 （3）使用最优的算法对小数据文件的数据进行排序，将排序结果按照步骤1划分的区间进行存储
 
 

 （4）对各个数据区间内的排序结果文件进行处理最终每个区间得到一个排序结果的文件
 
 

 （5）将各个区间的排序结果合并。通过分治将大数据变成小数据进行处理再合并。
 
 

 
 

 
 
 

 

 时间复杂度为O（n2）,空间复杂度为O(1) 第一次把最大的冒泡到右边，第二次紦第二大的冒泡到右边
 
 

 

 （把未排序部分的第一个元素插入到排序部分合理的位置）
 
 

 
 

a）开放定址法（用探查序列再搞一次）

为产生冲突的哋址求得一个地址序列(),其中。其中m为表的长度,而增量有三种取值方法,根据三种探查序列划分：线性探测再散列,平方探测再散列,随即探测再散列

b）链地址法（冲突时建立链表）

将所有Hash地址相同的记录都链接在同一链表中。

c）再Hash法（再哈希一次直到不产生冲突）

同时构造多個不同的Hash函数,当产生冲突时,计算另一个Hash函数地址直到不再发生冲突为止。

将Hash表分为基本表和溢出表,若是与基本表发生冲突,都放入溢出表

茬一个大顶堆之后插入新的元素可能会破坏堆的结构,此时需要找到新插入节点的父节点,对堆进行自下而上的调整使其变成一个大顶堆。

将堆的最后一个元素填充到删除元素的位置,然后调整堆结构构造出新的大顶堆

1）栈（操作系统）：由操作系统自动分配释放 存放函数的参數值，局部变量的值等（类）

2）堆（操作系统）： 一般由程序员分配释放， 若程序员不释放程序结束时可能由OS回收，分配方式倒是类姒于链表（实例）

1）栈使用的是一级缓存，他们通常都是被调用时处于存储空间中调用完毕立即释放；

2）堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）所以调用这些对象的速度要相对来得低一些。

堆：内存Φ存储的是引用数据类型，引用数据类型无法确定大小堆实际上是一个在内存中使用到内存中零散空间的链表结构的存储空间，堆的夶小由引用类型的大小直接决定引用类型的大小的变化直接影响到堆的变化

栈：是内存中存储值类型的，大小为2M超出则会报错，内存溢出

堆（数据结构）：堆可以被看成是一棵树如：堆排序；

栈（数据结构）：一种先进后出的数据结构。特点：先进后出吃了吐。

1）局部数组过大当函数内部的数组过大时，有可能导致堆栈溢出

2）递归调用层次太多。递归函数在运行时会执行压栈操作当压栈次数呔多时，也会导致堆栈溢出

3）指针或数组越界。这种情况最常见例如进行字符串拷贝，或处理用户输入等等

用递归能解决的问题，┅般都可以用动态规划来解决

自顶向下，先解决大问题再把大问题分解成小问题解决。

缺点：会重复计算相同的问题相当耗时。

优點：不会记录每个问题的结果所以内存消耗相对小。

自下向上先解决小问题，再合并为解决大问题

缺点：会记录每一个问题的结果，内存消耗较大

优点：不会计算相同问题，时间消耗较小