澹台千儿

# 单源最短路问题 # 基本概念 # 初始化 初始化过程定义顶点的最短距离 d[v] , 边权值矩阵 w[u][v] 和前驱数组 pi[v] . initializeSingleSourcevoid initializeSingleSource(Graph G, int s) { for (int v:G.vertices) { d[v] = INT_MAX; pi[v] = NULL; } d[s] = 0; // source}# Bellman-Ford...

# 概述 # 稳定性 稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 RRR 和 SSS，且在原本的列表中 RRR 出现在 SSS 之前，在排序过的列表中 RRR 也将会是在 SSS 之前。 基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。 选择排序、堆排序、快速排序、希尔排序不是稳定排序。 # 快速排序 该部分内容来自算法导论。 快速排序是基于归并的原地排序算法，期望时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn), 最坏时间复杂度...

# 单变元微分学 # 定义 # 可微 设函数 fff 在某邻域 U(x0,δ)U(x_0, \delta)U(x0​,δ) 内有定义，则若 ∃A∈R\exists A \in \mathbb{R}∃A∈R (AAA 是不依赖于 xxx 的常数) 使得 f(x)=f(x0)+A(x−x0)+o(x−x0)f(x) = f(x_0) + A(x-x_0) + o(x-x_0) f(x)=f(x0​)+A(x−x0​)+o(x−x0​) 当 x→x0x \to x_0x→x0​ 时成立，则称 fff 在 x0x_0x0​ 处可微 (differentiable), 并称...

# 级数 # 数项级数 数项级数的基本收敛判别是采用定义和柯西收敛准则判别。 # 定义 对级数 ∑n=0∞an\sum_{n=0}^\infty a_n∑n=0∞​an​, 定义部分和 (partial sum) Sn≔∑k=1nakS_n \coloneqq \sum_{k=1}^n a_k Sn​:=k=1∑n​ak​ 若部分和数列收敛，则称该级数收敛。反之，若部分和数列发散，则称该级数发散。 # 正项级数 对于正项级数，下述三种判别方法比较常用。分别是： 达朗贝尔判别法 (d'Alembert) 拉比判别法 (Raabe) 柯西判别法 (Cauchy) #...

# 存储系统原理 # 存储系统分类 存储系统包括： cache 存储系统 包括 cache 和主存 目的是提高存储器速度 虚拟存储系统 包括主存和硬盘 (辅存) 目的是扩大存储器容量 # 存储系统层次结构 通用寄存器 高速缓存 主存储器 辅存储器 脱机大容量存储器 # 存储系统的速度 若 H=N1/(N1+N2)H=N_1/(N_1+N_2)H=N1​/(N1​+N2​) 是命中率，则访问周期为 T=HT1+(1−H)T2T = HT_1 + (1-H)T_2T=HT1​+(1−H)T2​. H→1H \to 1H→1, 则 T→T1T \to...