3
7
2016
0

渐进记号中的对数

话说曾经和神犇JYT讨论过不同底数的对数在渐进记号中是否相等,即对于常数$a,b$,$\Theta\left(log_a n\right)$是否等于$\Theta\left(log_b n\right)$。我当时认为是不相等的,显然我是傻掉了。。。

根据对数的换底公式,$\log_a n=\large{\frac{\log_b n}{\log_b a}}$,因为$a,b$是常数,所以它们只相差常数倍。。。

Category: 算法及其他知识 | Tags: 数学
1
29
2016
0

组合计数及组合数取模问题

考虑这样一个问题:给出非负整数$n,m$和正整数$p$,分别求${n\choose m}\bmod p$。

在许多题目中都要解决这样的问题。

这片博客主要讨论的就是解决该问题的一些算法。

1
1
2016
0

简单数论算法

一些很基础的数论算法。

数学太弱了,写得烂,没什么办法。

本文大量参考、引用《算法导论》第31章内容。

Category: 算法及其他知识 | Tags: 数论 数学
12
26
2015
0

快速傅里叶变换(FFT)

多项式乘法是$FFT$的一个很常见的应用,所以就从它开始讲起。

Category: 算法及其他知识 | Tags: 数学
12
6
2015
0

几种二叉搜索树及其性能测试

二叉搜索树(BST)是很实用的一种数据结构,通常用于实现集合的维护和查询功能。

这里就讨论几种常见的BST,并对它们在实际情况中的性能表现进行测试。

12
5
2015
0

用后缀数组解决字符串相关问题

后缀数组由字符串的所有后缀排序后得来,可以高效地处理一些字符串问题。

Category: 算法及其他知识 | Tags: 字符串
12
5
2015
0

使用AC自动机进行多模板串匹配

KMP算法可以在$\mathcal{O}\left(n+m\right)$的时间内高效地完成单个模板串的字符串匹配问题。但是对于多模板串的情况,算法的时间复杂度只有$\mathcal{O}\left(\sum\left(n+m_i\right)\right)$,就不能满足需求了。

这时可以考虑使用AC自动机。

Category: 算法及其他知识 | Tags: 字符串
12
5
2015
0

精确覆盖问题和DLX

新学的东西,然而除了用来做数独以外并没有什么卵用。

Category: 算法及其他知识 | Tags:
10
4
2015
0

斯特林数和贝尔数

我数学弱,写得差不要怪我。

8
1
2015
0

01分数规划

今天碰到了一道神题,想了很久都没想出来,看了题解才知道要用01分数规划,然而我太弱了并不知道这是什么东西……

于是专门学习了一下01分数规划,发现真是个神奇的东西……

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com