Browsed by
Category: 算法与数据结构

随机化算法浅谈(2)

随机化算法浅谈(2)

上一篇我们谈到了求整数的因子的一种随机化的Polland算法,继续随机化算法的话题,我们讨论另外一类随机化算法——蒙特卡洛方法。 二、蒙特卡洛方法:M-R质性测试 相对于拉斯维加斯方法,随机化算法中还有一类叫作蒙特卡洛方法,它的基本思想是:每次运行随机生成问题的解,其中有一部分可以判断真假,另一部分…

Read More Read More

随机化算法浅谈(1)

随机化算法浅谈(1)

大家好,今天我们来聊一聊随机化算法。所谓随机化算法,就是将算法中某些关键步骤交给随机数去决定。 看到这里,可能有的朋友就觉得这太不靠谱了!不过在之前的学习中,大家一定也接触过这种优化思想,例如在快速排序中可以通过随机选择元素作为主元,相比于选首元素作为主元的快速排序对有序序列的\( O(N^2) \…

Read More Read More

上楼梯问题 – Advanced

上楼梯问题 – Advanced

Alice想登上N阶的楼梯,每一步Alice可以上一阶也可以上两阶,问登上N阶楼梯总共有多少种方法。稍有编程基础就知道这符合Fibonacci数列,因为Alice上N阶楼梯的走法F(n) 等于它走N-1阶的方案与N-2阶的方案之和,即F(n) = F(n-1) + F(n-2)。 现在Bob也想上N…

Read More Read More

字符串前缀问题:Trie树

字符串前缀问题:Trie树

Trie树主要是解决字符串前缀的搜索问题,例如最短前缀、某个前缀所含的字符串数等等。这是一种为解决一类字符串问题的树,与用于查找的树结构不同的是,Trie树需要在树的边上保存数据,这样组织一棵Trie树就需要有边节点和顶点节点。 一个Trie树是多叉树,根结点为空,树的边表示一个字母,顶点保存字符串…

Read More Read More

锦标赛排序:多路归并

锦标赛排序:多路归并

利用树结构进行排序是很常见的,例如查找树中序遍历就得到有序序列,使用堆结构也可以实现排序。这里的“锦标赛排序”就构造了一种“赢者树”的结构来实现排序。 一棵赢者树分为内部节点和外部节点。外部节点就是原始的数据,内部节点指向外部节点索引(比如外部节点的数组下标),一般为了便于计算,我们将外部节点的数据…

Read More Read More