Yuchen You

继电器 relay 输入小电流，输出大电流，起到中继的作用 为什么bug和虫子是一个意思？ 在早期ibm制造的继电器计算机中，经常会在故障的继电器中找到死掉的虫子，于是我们称计算机的问题为 bug 真空管 热电子发射是真空条件下加热金属的时候电子从材料表面逸出的现象 每一秒可以开闭数千次 与非门 符号 NAND 这是一切逻辑门的基础，我们首先要用原理图来认识它 从这里我们可以看出与非门最简单的形式就是采用两个开关进行控制，但是电路里面要实现自动化，我们就不能用销号人力的开关了，不如使用三极管，通过给基极传输高低电平实现通断来完成开关的功能 TTL 与 CMOS 控制 以下两个电路我们分别使用 TTL 和 CMOS 电路来实现功能 非门 通过将与非门两个输入端接入输入信号就是非逻辑了 与门 将与非门和非门串联 或非门 通过 德摩根定律，利用 A‾+B‾=A⋅B‾\overline{A}+ \overline{B} = \overline{A \cdot B}A+B=A⋅B 我们可以用两个输入分别取非逻辑实现或非门 或门 通过串联或非门和非门实现 恒高电平 ON 将非和原逻辑接入或 ...

全加器 考虑进位的加法称为全加，能够完成全加运算的电路称为全加器，一个基本全加器能够完成两个一位二进制数的全加运算，因此它具有三个输入端和两个输出端，其中 Xi,YiX_i, Y_iXi​,Yi​ 为加数，Ci−1C_{i - 1}Ci−1​ 相邻低位进来的进位数， SiS_iSi​ 为输出和，CiC_iCi​ 为向高位邻位进位数 和位 我们称 s 是和位输出，计算方法是对于 x_i, y_i c_i-1 的异或结果 s=x⊕y⊕cs = x\oplus y\oplus c s=x⊕y⊕c 那么在实际电路中我们只有二元输入的异或门，那么我们就可以用两个异或门进行组合完成 12xor g1(a,x,y);xor g2(s,a,c); 进位位 在三个变量中有两个变量是1的时候发生进位 c=(x⋅y)+(x⋅c)+(y⋅c)c = (x\cdot y) + (x\cdot c) + (y\cdot c) c=(x⋅y)+(x⋅c)+(y⋅c) 考虑到我们需要使用尽量少的逻辑门，那么我们需要对这个逻辑表达式进行化简 c=x⋅y+x⋅c+y⋅c=x⋅y+c⋅(x+y)c = x\cdot y + ...

O(1) — 常量空间复杂度 不管输入数据的规模如何，算法所需的内存空间大小是固定的。 数组中查找最大元素。这个操作只需要一个变量来保存当前找到的最大值，因此空间复杂度是O(1)。 O(log n) — 对数空间复杂度 需要的空间随输入数据的规模的对数增长。 递归实现的二分查找。在每次递归调用中，问题的规模都减半，因此最大的调用深度是log n，相应地，栈的空间也是O(log n)。 O(n) — 线性空间复杂度 需要的空间与输入数据的规模成正比。 动态数组（如C++中的 std::vector）。动态数组可能需要根据输入数据的数量动态调整大小，其空间复杂度通常是O(n)。 O(n log n) — 线性对数空间复杂度 空间复杂度介于线性和平方之间，通常见于一些特殊的排序算法中。 归并排序。在归并排序中，虽然每次合并操作都需要O(n)的空间，但由于其递归的性质，通常需要O(log n)层递归调用，因此整体的空间复杂度可能表现为O(n log n)。 O(n^2) — 平方空间复杂度 需要的空间与输入数据的规模的平方成正比。 一些特定的算法问题，如存储一个n x n的二维数组。

O(1) 常见的就是直接访问一个数组中某个元素的内容 这种算法一般不会受到输入数据大小的影响 1return array[i]; O(n) 线性时间复杂度，一般是遍历一阶数组中的所有元素 这会随着输入数据量的大小线性增大 O(log n) 对数时间复杂度，一般自常见的是用在对分查找。 或者常见的 m 叉树结构我们有 O(logmn)O(log_m n)O(logm​n) 的时间复杂度 O(n log n) - 线性对数时间复杂度 归并排序或快速排序。 说明：这些排序算法在最好或平均情况下的时间复杂度为n log n。 具体的算法的时间复杂度我们会在后面的细节讲解中提及. O(n^2) - 平方时间复杂度 冒泡排序或选择排序。 说明：这类算法通常涉及双重循环，对每对输入元素都进行操作。 容易搞混的地方在于，我们看每一层循环都容易看出是 一阶复杂度，然后我们会认为直接加起来就是一阶求和还是一阶复杂度，这就不对了 冒泡排序的时间复杂度推导 从最差角度考虑，冒泡排序需要比较 + 替换相邻元素的次数是 (n−1)+⋯+1=n(n−1)2(n - 1) + \cdots + 1 = \frac{n ...