算法-数学知识

这部分内容有下面几块

1
2
3
4
1、 数论
2、 组合计数
3、 高斯消元
4、 简单博弈论

一、数论

1、质数

1、判断质数

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

说明

1
2
3
4
5
·试除法
·判断条件的选择
	i < n和i <= n / 2时间复杂度都是O(n), 过高
	i * i <= n虽然时间复杂度是O(n^½ ), 但i * i可能会溢出
	因此最好的判别条件是i <= n / i，时间复杂度是O(n^½ )
2、分解质因数
1
2
3
4
5
6
7
8
9
10
11
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )              // 注意循环条件
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0) x /= i, cnt ++ ;
            cout << i << ' ' << cnt << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;    // 至多存在一个大于sqrt(n)的质因子
}

说明

1
2
3
4
·试除法
·数学知识：n 最多包含一个大于√n的质因子。例如6 = 2 * 3，,6 = 2.44949，存在一个大于√6的质因子 3
·判别质数用 i <= n / i条件
·最好时间复杂度O(logn), 最坏的时间复杂度O(n^½)