算法

简介

算法的概念

时间复杂度

空间复杂度

概念：按照某种顺序逐个列举或访问集合中的所有元素

时间复杂度：线性枚举的时间复杂度为 O(nm)，其中 n 是线性表的长度 m 是每次操作的量级。由于线性枚举需要遍历表中的每个元素，所以在处理大规模数据时，可能需要采用更高效的算法来提高搜索速度。

优化算法：

二分查找：如果线性表已经排序，可以使用二分查找来提高搜索效率。

哈希表：可以使用哈希表来存储已经搜索过的元素，避免重复搜索。

前缀和：可以存储前 i 个元素的和，避免重复计算。

双指针：可以从两端开始搜索，提升搜索效率。

概念：模拟现实世界中的某些过程或系统，以便进行预测、分析或解决问题。

时间复杂度：模拟算法通过建立数学模型来模仿实际系统的行为，然后在计算机上运行这些模型，以观察和分析系统在不同条件下的表现。故而没有固定的时间复杂度

概念：递推最通俗的理解就是一种数列，递推和数列的关系好比算法和数据结构，是一种循环和迭代的枚举过程

该数列由 0 和 1 开始，后面每一项的数字都是前两项数字的和

F(0) = 0, F(1) = 1

F(n) = F(n - 1) + F(n - 2), n > 1

该数列类似于斐波那契数列

T(0) = 0

T(1) = 1

T(2) = 1

T(n) = T(n - 1) + T(n - 2) + T(n - 3), n > 2

长度为 n (1<= 40 < 40) 的只由 ‘A’, ‘C’, ‘M’三种字符组成的字符串（可以只有其中一种或两种字符，绝对不能有其他字符）且禁止出现 M 相邻的情况，问这样的串有多少种？

考虑长度为n，且以 ‘A’ 结尾的串有f[n][0]种，以 ‘C’ 结尾的串有f[n][1]种，以 ‘M’ 结尾的串有f[n][2]种，那么我们要求的答案就为：

$\sum_{i=0}^2f[n][i]$

如果第 n 个结尾的字符是 ‘A’ 或者 ‘C’, 那么显然，第 n - 1 个字符可以是任意字符；而如果第 n 个结尾的字符是 ‘M’，那么第 n - 1 个字符只能是 ‘A’ 或者 ‘C’。所以我们可以得到递推公式如下：

$f[n][0]=f[n-1][0]+f[n-1][1]+f[n-1][2]\\f[n][1]=f[n-1][0]+f[n-1][1]+f[n-1][2]\\f[n][2]=f[n-1][0]+f[n-1][1]$

到这一步，已经可以利用程序求解了，但是仍然可以化简，由于：

$\sum_{i=0}^2f[n][i]=f[n][0]+f[n][1]+f[n][2]$

于是，可以得出：

$f[n][0]=\sum_{i=0}^2f[n-1][i]\\f[n][1]=\sum_{i=0}^2f[n-1][i]\\f[n][2]=\sum_{i=0}^2f[n-2][i]+\sum_{i=0}^2f[n-2][i]$

从而得到：

$\sum_{i=0}^2f[n][i]=2*(\sum_{i=0}^2f[n-1][i]+\sum_{i=0}^2f[n-2][i])$

令

$g[n]=\sum_{i=0}^2f[n][i]$

原式可以化简为如下递推式：

$g[n]=2*(g[n-1]+g[n-2])$

由此我们通过手动地简单计算，得到长度为1以及长度为2的串的方案数目，可得伪代码如下

long long getACM(int n){
	long long g[40];
	g[1] = 3, g[2] = 8;
	for(int i = 3; i <= n; ++i){
		g[i] = 2 * (g[i - 1] + g[i - 2]);
	}
	return g[n];
}