树

  • 性质

    所有结点度数之和+1(根节点) = n(总结点数)

    初始归并段要增加几个0

    ①n=nk+n0

    ②n=knk+1

    二叉树：n0=n2+1

    叶节点数 = 度为2的结点数+1

    ①n=n0+n1+n2

    ②n=n1+2n2+1

    ①所有种类结点的和=n总结点数

    ②结点数 x 度数 的和 +1(根节点)= n总结点数

(小括号)：默认向上取整

  • ==二叉排序树(查找树) BST==

    **查找：**Olog2(n) 次数不超过深度。

    左<根<右

    目的不是排序，而是提高插入、删除、查找的速度。

    插入：

    插入后从上往下，最后的位置一定是叶节点。从根开始比较，小就往左，大就往右，最后一定是叶子结点。

    删除：

    1. 叶节点不动；
    2. 有一个左/右子树，则子树替换被删结点。
    3. 有两个子树，用直接中序后继(前驱)替换。

  • ==平衡二叉树 AVL==

    定义：平衡因子<=1。

    **查找：**Olog2(n) 次数不超过深度。

    旋转：删除看个头，插入向上找

    插入：

    ①和BST一样。

    ②若插入后破坏平衡，则向上找到最近的最小不平衡树(祖先)。

    根据不平衡祖先和插入节点的相对位置进行（LL、RR、LR、RL）旋转。

    删除：

    ①和BST一样。

    ②若删除后破坏平衡，则向上找到最近的最小不平衡树(祖先)Z。

    根据Z的个头最高的孩子X，与X个头最高的孩子Y，X和Y的相对位置进行（LL、RR、LR、RL）旋转。

    最多次数：满二叉树

    最少次数：N1=1 , N2=2, Nn=Nn-2+Nn-1+1

  • ==B树 B-tree==

    **定义：**平衡因子为0，外部节点为null，叶子节点指内部节点最后一层。(终端结点同叶子结点)

    BST、AVL都是内存里小数据量检索。B树更适合大量数据（涉及硬盘）的检索。结点是硬盘，节点内部从硬盘读入内存后看到。

    m阶

    根的关键字：[1,m-1]

    非根关键字：[(m/2)-1,m-1] <从阶数一半开始>

    子树是关键字个数+1。

    查找：循环查找：①（磁盘里操作）比较后找到左/右子树的结点，从磁盘读入内存。②（内存里操作）结点内部找目标关键字（折半或顺序）

    插入：

    ①定位：根据BST查找算法，找到外部节点的NULL的位置。

    （书里的原话是，查找到叶子节点NULL后，再定位到父结点）

    ②插入：插入后检查结点是否在[(m/2)-1,m-1]。若个数大于m-1，进行分裂。

    ③分裂：根据(m/2)的位置分成左中右三部分。

    • 中间位置的关键字插入父节点（左右子树分别为左部分右部分结点）。
    • 左部分结点保留原结点。
    • 右部分节点作为父结点的新右子树。

    (m/2)是上取整。

    构建B树时，要增加子树只能通过分裂。

    分裂后父节点必增加一个关键字。

    增加后超越上限（m/2），则继续分裂。

    删除：

    根据被删元素是——

    1. 非终端结点：用前驱或后继替代。

      删除非叶结点元素最终都转换成删除叶结点元素。（用叶节点给被删父节点填坑）

    2. 终端结点：根据被删关键字结点的个数——

      • />(m/2)-1：删完不低于下限，直接删。

      • =(m/2)-1:删完低于下限。

        从不满足关键字个数的结点视角看：

        那个孤零零的结点的视角：

        ①有兄弟够借：父下来，兄上去。

        被删结点相邻的兄弟关键字个数>(m/2)-1，以右兄弟为例，让被删结点后继即父结点关键字加入自己的节点，而后继的后继填补父结点关键字原位置。

        左右兄弟都可以借。

        后继 即双亲节点的关键字，后继的后继 即右兄弟最左边的关键字。

        左兄弟则是前驱和前驱的前驱。

        (原因是要保证有序的性质)

        ②左右兄弟都不够借：父下来，同合并

        此时左右兄弟的关键字都=(m/2)-1或无， ，合并为一个子结点。

        左右兄弟都可以合并。（左前驱右后继）合并时要带上子树。带子树的位置你观察关键字顺序就能知道在哪。

        合并后的双亲节点一定少了一个关键字，成为两个合并结点的中间关键字了。

        若双亲节点合并后，减少一个关键字导致<(m/2)-1，则继续循环这一步（判断兄弟够借或不够借）

    **高度：**logm(n+1) <=h<=log(m/2)((n+1)/2)+1

  • ==B+树==

    适用于数据库检索。

    两层：分为目录层（分支）和数据层（叶子）

    关键字重复：非叶节点只负责索引（即指针），没有数据地址。所以查找就像坐电梯直达目标叶子节点。

    两个头指针：根节点一个指针，叶子节点一个指针。

    关键字和子树个数相等：一个关键字对应一个子树的最大元素。故关键字个数是m/2, 比B树+1。

    B+随机+顺序都支持。B仅支持随机

  • ==小根堆==

    **定义：**完全二叉树（叶子必须从左到右连续排列）。任一节点>=其左右孩子。

    • 节点i的左孩子：2i

    • 右孩子：2i+1

    • 父节点:(i/2) 下取整

    非叶子结点：1~(n/2)

    **输出：**输出堆顶元素后，将堆底元素送入堆顶，再慢慢下坠。

    **删除：**同输出。

    **插入：**先放堆底，再逐步上升。

    调整：普通数组变成根堆：从下往上看。

    将n除以二 向下取余，找到最后一个非叶节点。开始从后往前遍历所有非叶结点，不符合大小关系的就和孩子交换。

空间几何

旋转面：[平面曲线]绕[平面直线]，绕x轴则x不动，另外一个变平方和。
柱面：定直线为母线，定曲线为准线

平面：
点+截距=截距式
点+法向量=点法式

直线：
点+方向向量=对称式 / 参数方程

曲面积分

已知曲面的法向量用方向余弦表示是n = (cosα,cosβ,cosγ)。其中α是n与x轴(yoz面)的角度，β是与y轴(xoz面)，γ是与z轴(xoy面)。 而法向量用代数表示是n=(-Zx,-Zy,1) (当曲面为z=z(x,y)时)

第一类曲面积分，
求的是曲面表面的面积，也可以看作是高度为1的曲面薄片的质量。
方法是将三个方向的曲面面积投影到一个面上。

(利用梯度得到法向量，法向量与z轴的角度γ即xoz 和 yoz平面与投影面xoy的角度γ)

一个平面dS和另一个投影平面(如xoy)的夹角，即该平面切平面与对应坐标面的夹角，即切平面法向量与对应坐标轴的夹角。

侧边/斜边 = cosγ = 法向量n/z轴，即dS/dxdy = cosγ。 而cosγ = cos<n , z> = (n·z)/|n|·|z|

$$
d\sigma = dS \cdot \cos\langle \vec{n}, z轴 \rangle = dS\cdot\frac{\vec{n}\cdot z}{|\vec{n}|\cdot|{z轴}|} = dS\cdot\frac{(-Z_y,-Z_y,1)\cdot(0,0,1)}{\sqrt{(-Z_x)^2+(-Z_y)^2+(1)^2}\cdot\sqrt{0+0+1^2}}
$$

故dS = 1/cosγ dxdy 。
$$
dxdy = dS\cdot\cos\gamma => \frac{1}{\cos\gamma}dxdy = dS => S=\iint\limits_{D} \sqrt{Z_x^2+Z_y^2+1} , dxdy
$$

第二类曲面积分，
求的是单位时间截面通过的流体质量。 设流体密度为1，v是速度 s是面积，则 m=ρvts ，(vt是高，s是截面面积，故vts = V即体积 ,m=ρV)
方法同样是投影转换坐标，和第一类曲面积分类似，dydz = dScosα (此时dS=dxdy 1/cosγ) = dxdy(cosα/cosγ) ，此时由曲面法向量的代数表示得cosα/cosγ = -Zx。
故dydz = -Zx dxdy。同理dzdx = -Zy dxdy。

备注：解决第二类曲面还可以利用高斯公式和斯托克斯公式。
高斯要求曲面光滑+空间封闭(P对x偏导，Q对y偏导，R对z偏导, 积分微元统一为dV)，
斯托克斯则是将闭合曲线积分问题转换为以该曲线为边界的第二类曲面积分问题(公式+转换投影+二重积分)。

多播

ip 多播数据报，目的地址是 Ipv4 D 类地址，1110 开头，即 224 到 239。

分两种：本局域网的硬件多播 + 互联网的多播。

局域网硬件多播中，
mac 地址 只有 23 位能用作多播地址，

所以 ip 地址映射到 mac 时，只有后 23 位能保留。

这意味着映射不是一对一的。

PPP

咱们目前用的手机流量，就是数据链路层的点对点 ppp 协议。提到 ppp，就想起两个模块：link control protocols 和 net control protocol 。一个网络层协议对应一个 NCP。

ppp 首尾定界符：0X7E
ppp 面向字节，不需要序号确认，点对点不需要 csma 协议，所以没有最短帧长限制（2 匸 v），即 0-1500B

链接过程：
链路静止➡️链路建立➡️Lcp 协商成功进入鉴别状态➡️鉴别成功进入网络层协议状态，配置 Ncp➡️链路打开状态（此时可以通信了）

CSMA（介质访问）

csma/ca: 信道预约（监听）
隐蔽站：DIFS+RTS+［SIFS+CTS+（SIFS+数据帧+SIFS+ACK）］

csma/cd:边发边听。
二进制退避算法：0 到 2 τr。

（ r 是 2 的 k 次方-1k 为重传次数。）

k 最高为 10，到第 16 次不成功则放弃发送。

最短帧长：2 τ v（10Base 是 64B，51.2 微秒）

2 τv= RTT x V （往返时延 x 数据传播速率）

往返时延而非单程时延的原因：冲突信号需要从冲突点返回发送方 A 才能被检测到(边打边听)。

16 是个神奇数字。rip16 也是不可达

争用期：发送 64B(512b)的时间。

（端到端往返时间2τ，又称为碰撞窗口）

10Mbit/s 以太网是 51.2 微秒 的发送时间。

注意是bit位，不是按字节B。

100Mbit 是 5.12 微秒。同时会减少网段长度。

神奇的 fancy 公式：
2 的 n 次方 -1。

它是：
1.csma/cd 协议回避算法的最大退避时间。（第 n 次退避）
2.连续 ARQ 协议 gbn 的发送窗口上限。（n 比特对帧编号）
3.满二叉树的结点数（高度为 n）

TCP UDP IP MAC 首部长度

TCP 首部长度 20～60B。
(4位数据偏移字段 即首部长度，单位 4B，最大 15x4)

UDP 首部长度 8B

(2 2 2 2)

—————
以太网 MAC 帧：
首部长度：18B（不算前导码）

8 B 前导码（7 B 前同步码+1 帧开始定界符）

6 目的地址
6 源地址
2 交付协议类型
4FCS 检验码

数据：46-1500，
（46 时为帧最小长度 46+18=64B）

————
ip 数据报
首部长度 20B(可变长)

三单位 4B 1B 8B
总长度 16 位

10BASE和传输介质

T 是双绞线(Twisted)，F 是光纤(fiber)，数字是同轴电缆(cable)

  • 双绞线：

局域网+传统电话网，绞合减少相邻导线干扰，加上屏蔽层

适用于模拟传输（放大器）+数字传输(中继器)

  • 光纤：

光脉冲。

全反射特性。

长距离：单模光纤。直径小到一个波长，光会始终向前不反射。（用于半导体激光）

短距离：多模光纤。光源为发光二极管。

  • 同轴电缆：

强屏蔽性：内导体（铜芯）+屏蔽层+塑料外层

信道平均(实际)数据传输速率

=信道利用率×信道带宽(最大数据传输速率)”,

= 发送周期内发送的数据量/发送周期

BGP OSPF IGMP

BGP：
分为内部BGP协议(内部)和外部BGP协议(自治系统之间)，
iBGP内部会话，eBGP外部会话
打开、更新、保活、通知
(open,update,keepalive,notification)

OSPF：
1.问候分组(hello)
2.(数据库)描述分组
3.(链路)状态分组：请求、更新、确认

IGMP：传递多播信息
协议字段值为2，D类IP地址（前缀为1110，即224~239），局域网硬件多播时取后23位，还能互联网多播

边界对齐

边界对齐有两个要求：1.整体struct是最大变量对齐值整数倍；2.每个成员要按类型大小对齐(char1 short2 int 4)，或者说其地址对类型大小取余==0

拥塞窗口

我的意思是，拥塞控制窗口收到一个确认，才增加一个MSS。
比如慢开始为1，不超过拥塞控制初始阈值时，
第一轮RTT发送1个MSS，发送方收到一个确认则拥塞窗口cwnd增长为2。
第二轮RTT发送2个MSS，期间收到两个确认序号，2+2 = 4。
第三轮RTT发送4个MSS，期间收到四个确认序号，4+4=8。

这个期间，拥塞窗口cwnd是一个一个增长的，例如第三轮是4+1+1+1+1 = 8，收到一个接收方确认ack+1，而不是直接从cwnd=4收到一个累计确认直接到8。

例子：
cwnd = 1，ssthresh = 16。
发送方发送序号为 1-1000 的数据段（1 个 MSS）。
接收方收到后，回复 ACK 1001。这个ACK 1001就是一个累计确认，它确认了1-1000这段数据。
发送方收到ACK 1001后，知道1-1000已被确认。此时，“已发送但未确认” 的窗口为空。
根据慢开始算法，因为有一个 MSS 的数据被确认，所以cwnd增加 1，变为 2。
发送方现在可以发送 2 个 MSS 的数据，即 1001-2000 和 2001-3000。
接收方收到这两个数据段后，回复 ACK 3001。这个ACK 3001也是一个累计确认，它确认了1-3000这段数据（包括了之前的1-1000）。
发送方收到ACK 3001后，知道又有两个MSS 的数据（1001-2000 和 2001-3000）被确认了。
因此，cwnd会连续增加两次，从2变为4。

逻辑地址映射到物理地址

计算机为提升效率或保障安全，将“地址转换”作为“前置准备步骤”，与“最终是否真的读写数据”解耦。（故地址转换过程与cache无关。）

地址转换过程:
转换一个主存逻辑地址，根据硬件分成虚拟页号和页内偏移量offset，根据虚拟页号找到页表对应的页表项，先看有效位是否为1。

  • 如果为1直接把页表项里的物理页号和逻辑地址中的offset组合成为物理地址。
  • 如果为0，不看物理页号（没有意义），启动缺页中断程序，查页表项的外存物理地址，通过置换算法分配物理页框，把外存物理页调入内存并修改页表项的有效位、访问位等。
    处理程序完成之后，重新执行发生缺页的指令，得到访问页的物理地址。

——————

需要转换地址但不需要访问的情况
（不需要修改cache）

  1. CPU指令预取（最常见）：提前转地址，但指令可能被“丢弃”
  2. 内存保护与权限检查：转地址是为了“验证合法性”，而非“读写数据”

如果转换之后需要读写，则更新cache内容。

——————
注:
由于容量相差较大——
主存与外存的信息传输单位是 “页”page 或 “段”
主存与cache的信息传输单位是 “块” block。

实际上:
cache 块 = cache 行。
硬盘 块 = cluster 簇。

向量组

向量组是解决线性方程组的工具。
向量组的线性关系与线性方程组的对应如下:

设有两个向量组A和B。
A是mn矩阵，B是mt矩阵。
X即线性表示的系数，是n*t矩阵。
（即系数矩阵，即[k1k2……kn]。每个k对应B中一个列向量由A线性表示的系数）

1.向量组间的线性关系，对应非齐次线性方程AX=B。

1️⃣AX=B有解，A可通过系数矩阵X线性表示B
2️⃣如果无解，即B中至少有一个向量无法由A的向量线性组合得到

判断依据:有没有解通过看A矩阵与AB增广矩阵的秩是否相等。

注:
1.如果两个向量组等价，即相互线性表示，这意味着三秩相等。
2.B可退化成单个向量b，即向量组A是否可以线性表示b的问题。

2.向量组A自身内部的线性关系，对应齐次线性方程组。即AX=0。
1️⃣如果有唯一零解，就是向量组a线性无关，只能让k1=k2=……kn=0。
2️⃣如果无穷多解就是线性相关。

上述对应关系的核心是“秩”，而初等行变换是求矩阵秩的关键工具。
因此两者是分析线性关系与方程组解的分析工具。

关键路径、最短路径(dijkstra,floyd)

关键路径：

拓扑排序+逆拓扑

ete→lte
etv→ltv

dijkstra:

1.每次从未标记的节点中,选择距离出发点最近的节点，收录到最优路径集合S中
2.计算刚加入路径集合的节点A的所有邻近节点B的距离 (不包含标记的节点)
若(节点A的距离+节点A到节点B的边长)< 节点B的距离，就更新节点B的距离和前面点。

开始默认无穷，罗列顶点，分为第一轮第二轮第三轮，每一轮集合S增加一个顶点，该顶点不再延伸(后面几轮空白)。

floyd

n行邻接矩阵表示带权有向图。沿对角线n轮十字架，每轮对角线a[i] [i]不变(否则自己指向自己了)，对角线之外的元素值与十字架行列之和比较，小则替换。

Floyd可以求带负权边但不带负环图的多源最短路径

曼彻斯特编码

归零内部不跳变。

归零外部不跳变，两个固定样子；
非归外部零跳变，用跳变表示 01

曼彻斯特内部跳变，作为时钟信号。

曼彻斯特外部不跳变，两个固定样子；
差分曼彻斯特外部用跳变表示 01。

DHCP、ICMP、ARP

DHCP发现 提供 请求 确认报文

发现：源0 目255

提供：源服务器地址，目255

请求：源0 目255

确认：源服务器地址，目255

ICMP:(网际报文控制协议) 用于报告差错和异常情况。

分为差错报告报文和询问报文。
差错报告报文：
5个类型：终点不可达、源点抑制、时间超过、参数问题、改变路由（重定向）
4个不发送:ICMP报文自己、后续分片、多播地址、特殊地址的不发。

询问报文：
回送请求(和回答)
时间戳请求(和回答)
地址掩码请求(和回答)
路由器询问(和报告)

ARP（地址解析协议）

ARP请求分组 （广播）

ARP响应分组（单播）

ARP看到了IP地址，所以说网络层

NAT看到了端口，所以是传输层

MAC无法跨网络：主机想把IP分组发送到另一个网络，要用ARP找到网关（相邻路由器）的硬件MAC地址。而且路由器不会转发广播帧（ARP查询帧）。网关会把自己的MAC回复给主机。后续的传播任务交给路由器就好了。

中途源地址和目的地址会改变。

磁道

（柱面(磁道),磁头(盘面),扇区 ）

一个扇区的平均访问时间：寻道时间+旋转延迟时间+传输时间

Ts=mxn+s

m每跨越一个磁道耗时 s启动磁臂时间

Tr = r x1/2

r一秒几转

Tt=b/rN

b读写字节数，N一个磁道的字节

IEEE浮点数 阶码全0 尾数非0

尾数非零、阶码全0时属于「非规格化数」，

隐藏位为 0 且
指数为-126而非 0-127。

可以理解成“隐藏位的1 乘到阶码上了”。 隐藏位右移(除二)走，阶码+1位（乘二）

目的是让最大的非规格化数 0.f×2^-126 （尾数23位全1），恰好能和最小规格化数 1.0×2^-126 无缝衔接，不会出现数值断层。

0<f<1

阶码全1，尾数为0 正无穷大

阶码全1，尾数非0 无定义NaN

阶码全0，尾数全0 就是0（正负零）

阶码全0，尾数非0 非规格化数

规格化

浮点数运算时，需要规格化：确保尾数的最高位刚好在小数点之前。

左规：运算结果尾数的最高数位不是有效位，即0.000……的形式，进行左规。

尾数左移一位，阶码-1 （可能多次）

右规：运算结果尾数的有效位进到小数点前面时，右规。即1.xxx的形式，相加时最高进一位，故右规只需一次。

尾数右移一位，阶码+1（可能溢出）

运算：

  1. 对阶

    ①小阶向大阶看齐

    ②移位：左减右加（注意负数是算术移位，右移同符号位）

  2. 尾数加减

    隐藏位要还原到尾数

  3. 尾数规格化

  4. 舍入

    ①0舍1入:

    • 若舍弃部分的最高位是 0 → 直接舍去这部分，保留的最低位不变（“0 舍”）；

    • 若舍弃部分的最高位是 1 → 舍去这部分的同时，给保留的最低位加 1（“1 入”）；

    ②恒置1

  5. 溢出判断

    • 10,xxx 下溢出（按机器零处理）
    • 01,xxx 上溢出

kmp

next数组：当前位置不匹配时的最长公共前缀。

如果数组从1开始则需要整体+1,如果从0开始不需要。

模式串与主串匹配的公共前缀，显然不包括不匹配位置。所以是从当前位置往前看。

不匹配时，让数组和自己位置的next数组元素的模式串位置比较。

下面这个例子就是下标从1开始

要求那个next数组（有些叫next-val数组）：

1.必须先求模式串S 每一个字符前面的那个字符串的最大公共前后缀长度，将这一系列长度存成一个数组，求出来的每个长度其实就是和模式串每一个对应位置上做比较的下标 。

例如：模式串是 ABACABC 的最长公共前后缀长度数组为：

我们将最长公共前后缀长度记作LCPSF，现在从模式串第一个字符A开始，A的前面字符串为null，所以A之前的子串的LCPSF是0；来到B，B的前面字符串是A，A是单独的字符不存在公共前后缀，所以长度也是0；来到A，A前面的子串是AB，LCPSF为0；来到C，C前面的子串是ABA，LCPSF为1；来到A，A前面的子串是ABAC，LCPSF为0；来到B，B之前子串为ABACA，LCPSF为1；来到C，C前面子串为ABACAB，LCPSF为2；到此这个最长公共前后缀数组就出来了=【0,0,0,1,0,1,2】将这个数组从第二个值开始每个值加1=【0,1,1,2,1,2,3】就是将要和子串对应位置比较的下标

2.求得模式串最长公共前后缀的数组T【n】后，把模式串每个位置上的字符与这个数组存的下标对应字符作比较：

上面求出了下标数组【0,1,1,2,1,2,3】现在来和模式串ABACABC每个位置作比较求最终next-val数组：

next-val数组第一个数直接为0。 next-val第二数：模式串第二个字符为B，对应的下标数组第二个数是1，那就是将模式串的第1个字符和B相比较，A!=B,所以直接将下标数组第二个数1作为next-val数组第二个数的值 第三个数：模式串第三个字符为A，对应下标数组第三个数为1，取其作为下标，找到模式串第1个字符为A，A=A，那取next-val的第一个数做为next-val第三个数的值，也就是0 。。。。。以此类推，模式串每一个位置的字符和对应下标位置的数相等就取next-val中对应的数填到next-val中当前位置，不等就直接取当前下标数组的值填到next-val当前位置中

注意，这里所有序号，包括模式串和下标数组的数，第一个位置都是1，而不是常用的0开始

序号 1 2 3 4 5 6 7
模式串 A B A C A B C
下标数组 0 1 1 2 1 2 3
next-val 0 1 0 2 0 1 3

序号： 1 2 3 4 5 6 7

模式串 A B A C A B C

下标数组 0 1 1 2 1 2 3

next-val 0 1 0 2 0 1 3

中缀转前后缀

转前缀：符号移动到自己范围左括号的左边

转后缀：符号移动到自己范围右括号的右边

并查集/红黑树

并查集

每个子集合是一棵树，有一个根节点和一堆元素（叶子）。

元素下标为元素名。

元素值：

  • 正值表示自己所属集合根结点的下标。
  • 负值表示节点总数，自己是一个子集合的根

find(S,x):返回集合S中单元素x所在集合的根节点下标值。

O(n) 优化后→O(log2n) →压缩路径→O(a(n))

Initial(S)：把S的每个元素初始化为只有一个单元素的集合

O(n^2^) 优化后→O(nlog2n) →压缩路径→O(a(n))

Union(S,root1,root2):S的两个子集合root2加入root1

S的子集合root2的元素值改为root1的下标。

原本root2元素值是负值，即作为子集合根，所在集合的元素个数。

红黑树

性质：

1.根叶黑

2.黑路同

3.不红红（不相邻）

结论：

1.黑高为h的红黑树至少有2^h^-1个内部结点。

有n个内部结点的红黑树高度 h<= 2log2(n+1)

2.根到叶节点最长路径不大于最短路径2倍

3.新节点：根染黑 非根染红

各种性能指标

  • 进程调度单位：

cpu利用率，系统吞吐量，周转时间，等待时间，响应时间

笔记本

  • 计算机网络：

速率、带宽、吞吐量、时延（发送传播处理排队）、时延带宽积、往返时延、信道利用率

  • 流水线吞吐率、流水线加速比

  • 磁盘：

    一个扇区的平均访问：寻道时间+旋转延迟时间+数据传输时间

    (柱面(磁道)、盘面（磁头）、扇面)

  • 计组性能指标：

CPI：执行一条指令的时钟周期数

CPU执行时间、吞吐量、响应时间、MIPS、FLOPS

计组第一章，笔记本上也有。

数据结构：

时间复杂度、

ASL(访问成功/失败) ,散列表

排序算法稳定性

CRC校验码、海明码、二进制除法

ip 数据报首部检验和
udp 校验和

码分复用

快来参与讨论吧~