克鲁斯卡尔算法

April 15, 2018
算法

首先,克鲁斯卡尔算法是用来求最小生成树的。另一种求最小生成树的算法叫普林姆算法(Prim)。

...

普林姆算法

April 15, 2018
算法

普林姆算法也是用来求最小生成树的,与克鲁斯卡尔算法遍历边不同,普林姆遍历的是点。

普林姆算法同样基于贪心,以任意点为初始点,每次选取与已选点相连的边权值最小的边,并把与这条边相连的点加入已选点集合。

...

并查集

April 15, 2018
算法

使用并查集可以快速判断两个元素是否属于同一个集合。

...

Principal component analysis

January 8, 2018
机器学习

PCA (Principal component analysis) 是一种给数据降维的方法。

利用PCA,能将一堆高维空间的数据映射到一个低维空间,并最大限度保持它们之间的可区分性。

...

快速幂算法

September 30, 2017
算法

在c,c++语言中,并没有提供求幂的基本运算,通常我们需要自己写函数或者调用STL提供的函数。

一般情况下,我们写的求幂函数基本上都是循环累乘,时间复杂度为O(n)。虽说是线性的时间复杂度,但求幂运算作为基础运算,往往调用频繁,这时候即使是线性的时间复杂度也将变得难也接受。

利用快速幂可以快速计算底数的n次幂。其时间复杂度为 O(logn)

...

位运算的妙用

September 27, 2017
算法

对于一些特定问题,巧妙运用位运算能使解法异常简洁高效,同时,适当运用位运算也能对程序进行优化

...

筛法求素数

September 15, 2017
算法

假设要求n以内的素数

筛法求素数是用一个大小为n的数组,作为标记数组,如果没被标记到则为素数。

开始均为未标记。

从2开始,2没被标记,将2存入一个存素数的地方,然后筛掉小于n的,2的所有倍数。然后是3,筛掉3的所有倍数,依此类推,直到n-1。

...