C++ 标准模板库简介 C++ 标准模板库（Standard Template Library）是 C++ 标准库的一部分，不需要另外安装，直接导入即可使用。 STL 为程序员提供了通用的模板类，这些模板类可以用来实现各种数据结构和算法，从而使程序员不必从头开始编写这些代码。 STL 很好地实现了数据结构和算法的分离，大大降低了模块之间的耦合度，程序员可以自由组合 STL 提供的数据结构和算法。 STL 的核心由以下三个部分组成： 容器（Containers）：各种数据结构，如 vector、deque、map、set 等。 算法（Algorithms）：各种算法，如排序、查找、转换等。 迭代器（Iterators）：用于遍历容器的对象。 下面我们将从这三个部分来介绍 STL。 容器（Containers） 容器是用来存储数据的对象，它们提供了一种高效的方式来存储和访问数据。对于不同的任务，我们可以选择不同的容器来存储数据。 STL 的容器分为三类： 序列容器：序列容器会维护插入元素的顺序。常用的序列容器有 vector、deque。 关联容器：关联容器既有有序，也有无序，存储 ...
学习笔记
未读使用 PyPy 代替 CPython Python 的默认解释器是 CPython，它是用 C 语言实现的。由于 CPython 的执行效率比较低，因此在一些算法竞赛中，会使用 PyPy 代替 CPython。PyPy 是用 Python 语言实现的，它的执行效率比 CPython 平均高出 5 倍。由于某些 Python 早期发展历史原因，许多常用的第三方库都是针对 CPython 解释器进行设计和优化的，使用 PyPy 时可能会使程序变得更慢甚至无法运行，这也是 Python 仍把 CPython 作为默认解释器的原因。 但在日常的算法练习或是正规的算法竞赛中，往往都不会用到这样的第三方库，而 PyPy 的执行效率却比 CPython 高出很多，因此在这些场景中，使用 PyPy 代替 CPython 可以获得很大的加速效果。 使用 sys.stdin.readline 代替 input Python 自带的输入函数 input 可以读取一行输入，并把它以字符串类型返回。但是 input 的执行效率比较低，因此在一些算法竞赛中，会使用 sys.stdin.readline 代替 ...
列表 List 列表是 Python 中常用的容器之一，它的时间复杂度如下： 操作 平均时间复杂度 最坏时间复杂度 Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(n) O(n) Insert O(n) O(n) Get item O(1) O(1) Set item O(1) O(1) Delete item O(n) O(n) Iterate O(n) O(n) Get slice O(k) O(k) Del slice O(n) O(n) Set slice O(n+k) O(n+k) Extend O(k) O(k) Sort O(n log n) O(n log n) Multiply O(nk) O(nk) x in s O(n) min(s),max(s) O(n) Get length O(1) O(1) Python 中的列表是动态数组，它的底层是一个数组，当列表的长度超过数组的长度时， ...
简介 heapq 库是 Python 标准库中的一部分，它提供了一些堆操作的函数，可以用来实现优先队列。 优先队列是一种特殊的队列，它的每个元素都有一个优先级，元素的出队顺序是按照优先级从高到低的顺序进行的。优先队列的实现有多种方式，其中最常用的是堆。 堆是一种特殊的树，有两种类型，分别是最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。堆的根节点是堆中的最大值（最小堆的根节点是最小值）。 heapq 的大部分操作都是基于最小堆实现的，通过将元素取相反数，可以实现最大堆。 heapq 库的使用 heapq 库提供了 heapify、heappush、heappop、heapreplace、heappushpop、merge、nlargest、nsmallest 等函数，用于堆的操作。 heapify heapify 函数用于原地将列表转换为最小堆，时间复杂度为 O(n)O(n)O(n)。 函数原型如下： 1heapq.heapify(x) 其中，x 是一个列表。 示例： 12345import heapqx = [1, 3, ...
简介 bisect 库是 Python 标准库中的一部分，它提供了二分查找的功能。二分查找是一种在有序列表中查找某一特定元素的搜索算法。它的时间复杂度为 O(logn)O(\log n)O(logn)，比顺序查找的时间复杂度 O(n)O(n)O(n) 要有效率。 bisect 库的使用 bisect 库提供了 bisect_left、bisect_right、insort_left、insort_right四个函数，用于在有序列表中查找或插入元素。 bisect_left bisect_left 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，返回该位置，如果元素已经存在，则返回它的左边位置。 函数原型如下： 1bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None) 其中，a 是一个有序列表，x 是要查找的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。 示例： 12345678# 导入 bisect 库import bisect# 有序列表a = [1, ...
学习笔记
未读遗传算法 遗传算法是一种模拟自然界生物进化机制的优化算法，它通过模拟自然选择、交叉和变异等操作来寻找问题的最优解。 遗传算法通常包括以下步骤： 定义问题的目标函数和约束条件，以及变量的编码方式。 生成初始种群，即一组随机的可行解。 计算每个个体的适应度值，即目标函数的值。 选择操作，根据适应度值选择一部分个体进入下一代。 交叉操作，对选中的个体进行染色体的交换，产生新的个体。 变异操作，对某些个体的某些基因进行随机改变，增加种群的多样性。 重复3-6步，直到满足终止条件，如达到最大迭代次数或适应度值达到预设阈值。 输出最优解或最优解集。 MATLAB 实现遗传算法 MATLAB 中的遗传算法函数为 ga，其基本语法为： 1[x,fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon) 其中，fun 为目标函数，nvars 为变量个数，A 为不等式约束系数矩阵，b 为不等式约束右端项，Aeq 为等式约束系数矩阵，beq 为等式约束右端项，lb 为变量下界，ub 为变量上界，nonlcon 为非线性约束函数，intcon 为整数变量 ...
学习笔记
未读粒子群算法 粒子群算法是一种启发式算法，它的核心是思想是利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的可行解。 粒子群算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”和“变异”操作。 粒子群算法包括以下几个步骤： 预设参数，包括粒子个数、维度、迭代次数、惯性权重、学习因子等。 变量初始化，包括粒子的位置、速度、个体最优解、全局最优解等。 适应度计算，根据目标函数计算每个粒子的适应度值，并更新个体最优解和全局最优解。 速度和位置更新，根据粒子群算法的公式更新每个粒子的速度和位置，使其向最优解靠近。 自适应调整参数，根据迭代过程中的情况调整惯性权重等参数，使其能够平衡全局搜索和局部搜索的能力。 自动退出迭代，根据预设的终止条件判断是否退出迭代，如达到最大迭代次数、最优解变化小于阈值等。 MATLAB 实现粒子群算法 MATLAB 中的粒子群算法函数为 particleswarm，其基本语法为： 1[x,fval ...
学习笔记
未读马尔可夫链 马尔可夫链是一种随机过程，它的状态转移是由当前状态决定的，与过去的状态无关。马尔可夫链的状态转移矩阵是一个方阵，它的每一行元素之和为1，这样的矩阵称为概率转移矩阵。马尔可夫链的状态转移矩阵可以用来表示状态转移的概率。 MATLAB 马尔可夫链预测模型 例1 有一个时齐的马尔可夫链，其状态转移矩阵为： [0.50.30.20.20.60.20.40.20.4]\begin{bmatrix} 0.5 & 0.3 & 0.2\\ 0.2 & 0.6 & 0.2\\ 0.4 & 0.2 & 0.4 \end{bmatrix} 0.50.20.40.30.60.20.20.20.4 当前状态为第二个状态，求经过5步后的状态概率分布。 解 123456% 状态转移矩阵P = [0.5 0.3 0.2; 0.2 0.6 0.2; 0.4 0.2 0.4];% 初始状态x0 = [0 1 0];% 经过15步后的状态概率分布x5 = x0 * P^5 输出结果为： 12x5 = 0.3552 0.3949 0.2 ...
学习笔记
未读一元线性回归与多项式回归 MATLAB 提供了 polyfit 函数来进行一元回归，包括线性回归和多项式回归。 polyfit 函数的语法为： 1p = polyfit(x,y,n) 其中，x 和 y 分别为自变量和因变量，n 为多项式的阶数，p 为拟合多项式的系数。当 n 为 1 时，为线性回归。 使用 polyval 函数可以计算拟合多项式的值： 1y = polyval(p,x) 其中，p 为拟合多项式的系数，x 为自变量，y 为因变量。 例 使用线性回归拟合美国人口数据： 年份 1790 1800 1810 1820 1830 1840 1850 1860 1870 1880 1890 人口/百万 3.9 5.3 7.2 9.6 12.9 17.1 23.2 31.4 38.6 50.2 62.9 年份 1900 1910 1920 1930 1940 1950 1960 1970 1980 1990 2000 人口/百万 76.2 92.2 106.5 123.2 132.2 151.3 179.3 203.2 226.5 249.6 281 ...
学习笔记
未读人口增长模型 Malthus模型（指数模型） 最早的人口增长模型是 Malthus 于 1798 年提出的指数模型，基本假设是人口增长率 r 是常数。 N(t)=N0ertN(t)=N_0e^{rt} N(t)=N0ert 这个模型的问题在于，它没有考虑到人口增长的阻滞因素，即人口增长的上限。因此，当预测时间 t 较短时，模型的预测结果是合理的，但是当预测时间 t 较长时，模型的预测结果就会出现较大的误差。 Logistic模型（阻滞增长模型） 由于人口不可能无限制的增长，当人口达到一定数量后，那么增长率就会下降。因此， Verhulst 于 1838 年提出了阻滞增长模型，基本假设是人口增长率 r 随着人口数量 N 的增加而减小。 人口增长率 r 是一个关于人口数量 N 的线性函数： dNdt=r(N)N\frac{dN}{dt}=r(N)N dtdN=r(N)N 人口增长率 r 的函数形式为： r(N)=r−sN,(r,s>0)r(N)=r-sN,(r,s>0) r(N)=r−sN,(r,s>0) 其中， r 是人口增长率的最大值， s 是人口增长率的下降速率 ...
