《算法优化》专题

排序算法的评价 稳定性 稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。 计算复杂度（最差、平均、和最好表现） 依据串行（list）的大小（n），一般而言，好的表现是O(nlogn)，且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个

单链表 单链表就地翻转 递归算法： void reverse(struct list_node *head) { if(NULL == head || NULL == head->next) return; reverse1(head->next); head->next->next = head; head->next = NULL; } 非递归算

也称为跳跃表(Skip List)是一种基于【有序链表】的扩展，简称【跳表】。 存储的数据是有序的。 所以跳表对标的是平衡树（AVL Tree）和二分查找，是一种插入/删除/搜索都是O(log n)的数据结构。 它最大的优势是原理简单、容易实现、方便扩展、效率更高。 定义 增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。 跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链

分治和回溯其实本质上就是递归，只不过它是递归的其中一个细分类。可以认为 分治和回溯 最后就是 一种特殊的递归 或者是较为复杂的递归即可。 分治算法，即分而治之（divide and conquer，D&C），把 一个复杂问题 分成 两个或更多 的相同或相似 子问题，直到最后子问题可以简单地直接求解，最后将子问题的解合并为原问题的解。 分治法的核心思想就是，将原问题分解成小问题来求解，只要遵循三个步

链表的概念 逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表（数组）那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。 每个元素本身由两部分组成： 本身的信息，称为 数据域 指向直接后继的指针，称为 指针域 内存分布 数据是连续存储的，一个挨着一个，连续的。链表是存储单元不一定是连续的， 主要分类 单向链表 循环链表 双向链表 双向循环链表 单向

目标 在本章中，我们将理解k-最近邻（kNN）算法的概念。 理论基础 kNN是可用于监督学习的最简单的分类算法之一。这个想法是在特征空间中搜索最接近的测试数据。我们用下面的图片来看看它是怎么工作的。 在图像中，有两类家庭，蓝色方块和红色三角形。我们称每种家庭为一个为Class。他们的房子被显示在他们的城镇地图上，我们称之为特征空间。 (您可以将一个特征空间视为所有数据投影的空间，例如，考虑一个二维

目标 在这一章中我们将学习 BRIEF 算法的基础知识 理论基础 SIFT^2算法使用 128 维的向量描述符。由于它使用的是浮点数，因此它至少需要 512 字节。相似地，SURF^3 算法也至少需要 256 字节（64 维）。创建这样一个数以千计的特征向量需要大量的内存，这对于一个资源有限的应用，尤其是嵌入式系统上的应用来说是不可接受的。而且所消耗的内存空间越多，匹配花费的时间也越长。 但是实际

目标 在这一章中： 我们将理解 FAST 算法的基础 我们将使用 OpenCV 中的 FAST 算法来找出角点 理论基础 我们已经看过了几个特征检测器，而且其中许多效果相当好，但是从实时应用程序的角度看，他们还不够快，一个最好的例子就是SLAM^3（即时定位与地图构建），在这种情况下，机器人只有有限的计算资源。 作为这种情况的一种解决方案，FAST（Features from accelerate

1. Gibbs采样算法求解LDA的思路 首先，回顾LDA的模型图如下： 在Gibbs采样算法求解LDA的方法中，我们的$$alpha, eta$$是已知的先验输入,我们的目标是得到各个$$z_{dn}, w_{kn}$$对应的整体$$vec z,vec w$$的概率分布，即文档主题的分布和主题词的分布。由于我们是采用Gibbs采样法，则对于要求的目标分布，我们需要得到对应分布各个特征维度的条件概

在Spark MLlib中，推荐算法这块只实现了基于矩阵分解的协同过滤推荐算法。而基于的算法是FunkSVD算法，即将m个用户和n个物品对应的评分矩阵M分解为两个低维的矩阵：$$M_{m times n}=P_{m times k}^TQ_{k times n}$$ 其中k为分解成低维的维数，一般远比m和n小。如果大家对FunkSVD算法不熟悉，可以复习对应的原理篇。 2. Spark推荐算法类库

SimRank是基于图论的，如果用于推荐算法，则它假设用户和物品在空间中形成了一张图。而这张图是一个二部图。所谓二部图就是图中的节点可以分成两个子集，而图中任意一条边的两个端点分别来源于这两个子集。一个二部图的例子如下图。从图中也可以看出，二部图的子集内部没有边连接。对于我们的推荐算法中的SimRank，则二部图中的两个子集可以是用户子集和物品子集。而用户和物品之间的一些评分数据则构成了我们的二部

问题 你想快速计算某数的平方根倒数。 解决方案 在 Quake Ⅲ Arena 的源代码中，这个奇怪的算法对一个幻数进行整数运算，来计算平方根倒数的浮点近似值。 在 CoffeeScript 中，他使用经典原始的变量，以及由 Chris Lomont 发现的新的最优 32 位幻数。除此之外，还使用 64 位大小的幻数。 另一特征是可以通过控制牛顿迭代法的迭代次数来改变其精确度。 相比于传统的，该算

本教程将全面介绍深度学习从模型构造到模型训练的方方面面，以及它们在计算机视觉和自然语言处理中的应用。

参考资料：http://www.cs.ucsb.edu/~xyan/papers/gSpan.pdf http://www.cs.ucsb.edu/~xyan/papers/gSpan-short.pdf http://www.jos.org.cn/1000-9825/18/2469.pdf http://blog.csdn.net/coolypf/article/details/8263176更

参考资料：http://baike.baidu.com/link?url=vlCBGoGR0_97l9SQ-WNeRv7oWb-3j7c6oUnyMzQAU3PTo0fx0O5MVXxckgqUlP871xR2Le-puGfFcrA4-zIntq更多挖掘算法：https://github.com/linyiqun/DataMiningAlgorithm 介绍 RoughSets算法是一种比较新颖的