译码器和编码器

随笔:

1. 译码器是n个输入，2^n个输出；编码器是2^n个输入，n个输出。编码器就是译码器的反向操作。一种输入组合的二进制数，对应一种输出组合的二进制数(n位输入能组合出2^n种输出)。
2. 对于优先编码器，就是只看最大编号的那一位，小于这位编号的都忽略，所以这些被忽略的称为无关项。

三态缓冲器

随笔: 三态就是”三个状态”: 0、1、开路(断路)。然而开路相当于连接了一个阻值非常高的电阻。

使能端(Enable)

随笔: 使能端是用来控制多路选择器是否工作的。当使能端为0时，多路选择器不工作，输出为0；当使能端为1时，多路选择器工作，输出为输入端的值。详细展开说：给四位输入，假设从左往右画，4个或门1个与门，左侧是输入端右侧是输出端。

输入端：

1. 输入I（即I0 I1 I2 I3的串联状态）
2. 使能端E
3. 控制端A B（这里是四位输入所以要用两个控制端）

输出端：

1. 或门输出：（布尔表达式有四个变量：I||A||B||E=或门输出）
2. 与门输出 ：①号或门 && ②号或门 && ③号或门 && ④号或门=与门输出 （Z表示）

我们知道或门中只要有一个输入为1，输出就为1。当I=0 A=0 B=0这个状态时，由于当E=0，这一个或门它的输出是0，所以我们知道这一堆或门中至少有一个是0，导致最后的与门为0，实现了禁用这个多路选择器(MUX)。同理当E=1时那个或门是为1的，MUX正常工作(由控制端控制)。

多路选择器(MUX)

多路选择器(MUX)

随笔: 输出值取反的叫低有效输出，输出值不取反的叫高有效输出。实际上很好理解，因为取反需要一个反相器，而反相器的延时是有的，所以取反的输出会比不取反的输出慢一些，所以取反的输出叫低有效输出，不取反的输出叫高有效输出。

由全加器组成的行波进位加法器(串行加法器)

全加器(Full-Adder)

全加器(Full-Adder)是一种能够实现三个二进制数相加的电路，它的输入有三个二进制数，分别是Xi、Yi和Ci，输出有两个二进制数，分别是Si(代表Sum)和C(i+1)(代表Cout)。其中，Xi和Yi是要相加的两个二进制数，Cin是上一级的进位输出，Sum是相加的结果，Cout是输出的进位。

由全加器组成的行波进位加法器(串行加法器)

行波进位加法器(串行加法器)是由多个全加器组成的，它的输入有两个二进制数，分别是Xi和Yi，输出有一个二进制数，是相加的结果。其中，Xi和Yi是要相加的两个二进制数，Sum是相加的结果。

关于那些数据结构，如果要讨论他们的优劣性。我只能记住这么多：

数组

连续排列，所以省 空间 ，自带索引，所以查询时间复杂度低，缺点是插入和修改比较难，需要移动相当多的元素来为目标元素腾位置，时间复杂度高。

链表

不需要连续排列，所以占用空间比起数组要多一些， 优点：插入和修改操作简单，只需要改动相应的少数几个元素的指针指向。 缺点：查询时间复杂度高，需要查询整个链表才能找到 (这是最坏情况，看批运，因为没索引)

树

通常情况下讨论二叉树，时间复杂度比线性好，但可以被 退化 成链表，即失去所有左或者右子树 AVL 树和 B 树都是具有良好稳定性的树

堆

可以以树的方向理解，是一种特殊的 完全二叉树 ，这种数据结构是拿来存放诸如” 大量的 “” 带有冗余的 “” 不经常做查询的 “数据，对堆的查询会很复杂，但是插入比较简单：压到最底端，在完全二叉树下即右下方向，然后根据完全二叉树数值上左子树 ≤ 根 ≤ 右子树的性质，维护。

栈

先进后出的形式

队列

先进先出

哈希表

比起链表，在每个栈帧空间中除了元素数值，多存储一个指针，这样占用空间更多但是查询，删除修改和插入简单都是 O (1)，通过对应哈希函数做到，但是会遇见 哈希冲突 ，避免和解决哈希冲突 (也就是维护哈希表) 需要花费额外的时间复杂度和空间复杂度。

图

分有向图和无向图 有向图会为了存储方向花掉更多空间，而且限制会比无向图多，不够灵活，但是有向图也分为单向有向图和双向有向图，这个跟双向链表相似，不展开讲了
无向图非常灵活

总结：

数组，链表是线性数据结构时间复杂度 O (n) 开始，树是分治，时间复杂度 logn 开始 (n 叉树，对数的底数就为 n)

时间：2023-11-30 22:51:28

tags: 算法，数据结构，编程，数据结构与算法，数据结构与算法分析，数据结构与算法设计

作者：buynonsense

k

指的是：“我要发送的信息位”，原始信息位的数量（个数）。

r

校验位的个数

n

n=k+r 原始数据加上校验位 合起来的个数.

• 通过增加冗余的校验位来提升传输的数据.
• 核心公式 k+r+1<=2^r
• 配偶原则:让’1’的个数为偶数个 不可靠

奇偶校验

• 可以检测出是否有错,但是不能检测出哪位错

异或:操作数有奇数个1，结果为1 偶数个1，结果为0

奇校验 一个校验位+原来的数据位 ，使得代码中 1 的个数为奇数个。
偶校验 一个校验位+原来的数据位 ，使得代码中 1 的个数为偶数个。

需要注意的是，奇校验和偶校验只能检测到单一比特的错误，无法检测到多个比特的错误。

海明码

海明纠错码

是一种分组的奇偶校验.

• 分组非划分分组:组与组有重叠
  • 分成3组,每组有1位校验位,共包括4位数据位
  • pi的位置 在2^i-1
  • pi的取值 配奇/偶原则
• 需要记住：
  • 第一组：1，3，5，7
  • 第二组：2，3，6，7
  • 第三组：4，5，6，7

  • ---

  • 第四组：8，9，10，11

    ps:这里每组的数字都表示位置而不一定表示实际数值。而高亮的数字则是校验码(这里是从左到右)。 校验码的目的是使每一组在二进制数形式表示下的1的个数为偶数个。(默认我们使用的是偶校验/配偶原则)。所以如果位置的索引刚好对应此位置上的数值时，即这里的位置即表示位置又表示数值。这里的1,2,4,8是完美状态(即没有出错)

workbench 触发器和索引怎么配注:

• T-SQL是Transact-SQL的缩写，是一种用于管理和查询关系数据库的编程语言。它是Microsoft SQL Server数据库管理系统中使用的一种SQL方言。T-SQL不仅支持标准的SQL语法，还提供了额外的功能和扩展，使其更适合处理复杂的数据库操作和编写存储过程、触发器和函数等数据库对象。
• 视图（View）是一种虚拟的数据库对象，它代表一个基本表或其他视图的查询结果集。视图是一种抽象层，允许用户以更简单的方式访问和查询数据库中的数据，而不必直接操作表。

触发器

• 基本概念：触发器(Trigger)是用户定义在关系表上的一类由事件驱动的特殊存储过程。

  触发器（英语：trigger）是在数据库中，在执行对资料有异动的动作时，先行拦截并处理的一种数据库物件，它大部分会设在资料表中，作为强制执行特定动作的程序，因此又称为数据操纵语言（DML）触发器。——Wikipedia

• 触发器不能通过名称被用户直接调用，不允许带参数。

AFTER触发器、INSTEAD OF触发器

• (除了这两种主要的触发器类型，不同的数据库管理系统可能还支持其他特定类型的触发器。例如:PostgreSQL 还支持 “BEFORE” 触发器。)

AFTER触发器

1. AFTER触发器又称”后触发器”，该类触发器是在引起触发器执行的修改语句 (INSERT 、 UPDATE 或 DELETE) 成功完成之后执行的。如果中途失败，触发器不会执行。

2. 此类触发器只能定义在表上，不能创建在视图(view)上。

INSTEAD OF触发器

1. INSTEAD OF触发器又称为替代触发器，该类触发器是当引起的修改语句停止时执行的。

2. 既能在表上定义，也可在视图上定义。

3. 对于每个触发操作(INSERT 、 UPDATE 或 DELETE)只能定义一个INSTEAD OF触发器。

• 用途：可用于对一个或多个列执行错误或值检查，然后在INSERT、UPDATE或DELETE之前执行其他操作。

触发器技术是一种用于确保数据完整性和实现复杂业务规则的高级技术。相对于其他约束，触发器具有以下优点：

1. 自动执行（Automated Execution）：只要对表的数据进行修改，触发器会立即激活。

2. 级联更改（Cascading Changes）：触发器能够实现数据库中相关表的级联更改。(例如，在销售数据库中，可以为商品表的商品编号字段创建一个插入触发器，当向商品表添加新记录时，触发器会自动在商品销售表的商品编号中插入新的商品编号值。)

3. 数据完整性（Data Integrity）：触发器可用于实施数据完整性约束，确保数据在数据库中保持一致性和有效性。这包括检查外键关系、唯一性约束、检查约束等。(触发器能够实现比CHECK约束更为复杂的数据完整性约束。触发器可以包含复杂的处理逻辑，允许实现复杂的数据完整性约束。与CHECK约束不同，触发器可以引用其他表中的列，并执行其他操作，如修改数据或显示自定义信息。)

4. 应用程序逻辑（Application Logic）：触发器可用于执行应用程序特定的业务逻辑。在一个表中可以存在多个不同类型的触发器（INSERT、UPDATE或DELETE），这意味着对于相同的修改语句，可以有多个不同的响应策略。这提供了更大的灵活性。

5. 审计和日志（Auditing and Logging）：记录数据库操作历史，以帮助跟踪和回溯操作。

创建触发器

• 一个触发器由三部分组成：触发事件、触发条件、触发器动作体。
• 表的所有者具有创建触发器的默认权限，不能将该权限转授给其他用户。

格式一般如下：

CREATE TRIGGER <触发器名> ON <表名|视图名>
    { FOR | AFTER | INSTEAD OF} <触发事件>
AS
    <触发器动作体>
……

1. <触发器名> 不能以”#”或”##”开头。

2. <表名/视图名> 当这个表的数据发生变化时，将激活定义在该表上相应触发事件的触发器。视图只能被INSTEAD OF触发器引用。

3. AFTER 选项。用于SQL语句中指定操作都已成功执行时才被触发。所有级联操作和约束检查也必须在它之前完成。

   • 如果仅指定FOR关键字，则AFTER为默认值。

4. INSTEAD OF 选项。用于在原始SQL语句前指定操作（一个更高优先级的。）

   • 不可用于 使用WITH CHECK OPTION 的可更新视图。

5. 触发事件可以是INSERT|UPDATE|DELETE，也可以是它们的组合。定义触发器时必须至少指定一个触发事件。

6. <触发器动作体> 可以是一组T-SQL语句，也可以是对已创建存储过程的调用。

SQL Server触发器中delete表和inserted表

1. delete表存储着被DELETE和UPDATE语句影响的旧数据行。在删除和更新过程中，指定的数据行从基本表中删除，转移到delete表。所以一般来说基本表中和delete表中不会存在相同数据行。*(delete表作回收站)*

2. inserted表中存储着被INSERT和UPDATE语句影响的新的数据行。在插入和更新过程中，新的数据行添加到基本表，数据行的副本被复制到inserted临时表。

• 2个表都存在于高速缓存中。

• 由SQL Server自动创建管理，不允许用户修改。

• 一个典型的更新(UPDATE)事务由2个操作组成。1.旧数据行从基本表转移到delete表；2.新的数据行同时插入基本表和inserted表。即先删除再插入。

启用和禁用触发器

• 不同类型数据库的SQL语句也不同，这里以SQL Server举例。
  ALTER TABLE <表名>
  { ENABLE | DISABLE } TRIGGER { ALL | <触发器名> [,…n] }

修改和删除触发器

修改触发器的定义，可以使用ALTER TRIGGER语句。ALTER TRIGGER语句与CREATE TRIGGER语句的语法相似，只是语句的第一个关键字不同。
######
ALTER TRIGGER <触发器名> ON <表名|视图名>
{ FOR | AFTER | INSTEAD OF } <触发事件>
AS
<触发器动作体>

当不再需要触发器时，可以将其删除。只有触发器的所有者才有权删除触发器。删除一个或多个触发器，可以使用DROP TRIGGER 语句，语法如下。
######
DROP TRIGGER <触发器名> [,…n]
当某个表被删除后，该表上的所有触发器将同时被删除，但是删除触发器不会对表中数据有影响

概念

1. 基本操作单位：首先，确定算法中的基本操作单元。在大多数情况下，这是最内层循环的操作，例如比较、赋值、交换等。时间复杂度的计算通常是关于这些基本操作的数量。

2. 统计操作次数：分析每个基本操作在算法中被执行的次数。这通常涉及迭代、循环、递归等。确定每个操作的执行次数。

3. T(n)表示：使用T(n)表示算法的时间复杂度，其中n表示问题规模或输入大小。T(n)表示执行算法所需的操作数与问题规模n之间的关系。

4. 去掉常数系数：时间复杂度通常表示为大O符号（O），其中忽略常数系数和低阶项。例如，O(2n)通常简化为O(n)，因为常数系数2对于大问题规模而言不重要。

5. 最坏情况与平均情况：通常，我们关注算法的最坏情况时间复杂度，因为它提供了算法在最不利情况下的性能保证。平均情况时间复杂度可以在某些情况下提供更准确的信息，但通常更难分析。

基于上述原则，以下是一些常见的时间复杂度及其说明：

• O(1)（常数时间复杂度）：算法的执行时间与问题规模无关，是最高效的。典型的例子是数组索引或变量赋值。

• O(log n)（对数时间复杂度）：典型的例子是二分查找，其中问题规模每次缩小一半。

• O(n)（线性时间复杂度）：算法的执行时间与问题规模成正比。典型的例子是线性搜索。

• O(n log n)（线性对数时间复杂度）：典型的例子是快速排序和归并排序。

• O(n^2)（平方时间复杂度）：典型的例子是冒泡排序和插入排序。

• O(2^n)（指数时间复杂度）：典型的例子是某些递归算法，如斐波那契数列的朴素递归实现。

• O(n!)（阶乘时间复杂度）：典型的例子是旅行商问题的穷举解法。

浮点数

• 阶符号位＋阶码数值（范围）．＋数符号位．＋尾数精度

  • 定点整数　＋　定点小数

CLAIM1

• 尾数左/右 移几位，阶码就减/加 几。

CLAIM2

• 越向数轴的两端，刻度越稀疏。

CLAIM3

• 精度正比尾位
• 范围正比阶码

CLAIM4

规格化就是把小数点后的第一位为1.（通过乘右边的阶数移位做到。用来防止下溢丢失数值的问题。） 好处是提高精度。