问题
数学¶
函数连续性¶
函数连续性 函数 \( f (x) \) 在点 \( x = a \) 连续，当且仅当对于任意小的正数 \( \epsilon \)，总存在一个正数 \( \delta \)，使得当 \( x \) 与 \( a \) 的距离小于 \( \delta \) 时，函数值 \( f (x) \) 与 \( f (a) \) 的距离小于 \( \epsilon \)。直观上，这意味着函数在该点没有间断，其图像在该点是平滑连接的。 一致连续性 一致连续性是函数在整个区间上的一种更严格的连续性形式。函数 \( f (x) \) 在一个区间上是一致连续的，意味着对于任意小的正数 \( \epsilon \)，都存在一个正数 \( \delta \)，使得在这个区间内任意两个点 \( x \) 和 \( y \) 的距离小于 \( \delta \) 时，其对应的函数值 \( f (x) \) 和 \( f (y) \) 的距离都小于 \( \epsilon \)。与一般连续性不同，一致连续性要求在整个区间内的所有点对，都能使用同一个 \( \delta \) 来满足上述条件，这确保了函数在整个区间内变化不会太剧烈。
不相关与独立的区别¶
- 两个随机变量协方差为零时说明他们不相关，不相关是说不存在线性关系，但是可能存在非线性关系
- 如果联合分布可以由边缘分布直接相乘则随机变量相互独立，此时两个变量完全没有任何关系
编译原理¶
编译器的前端和后端都包含什么内容¶
- 前端：词法分析；语法分析；语义分析；中间代码生成
- 后端：中间代码优化；目标代码生成；目标代码优化
gcc 与 llvm¶
- gcc 传统编译器结构
- llvm 结构
- llvm 模块化设计：
- 使用统一的中间代码 llvm ir
- 如果需要支持一种新的编程语言，那么只需要实现一个新的前端；如果需要支持一种新的硬件设备，那么只需要实现一个新的后端
- 而优化是一个通用的针对 ir 的阶段
- 相比之下，GCC 的前端和后端没分得太开，前端后端耦合在了一起。
- GCC 是单体设计的传统编译器，前端、优化器和后端紧密耦合。LLVM 则是模块化设计，前端、优化器和后端松散耦合，使用统一的 LLVM IR。GCC 扩展难度大，而 LLVM易于扩展和修改。GCC 提供独立开发的完整工具链，LLVM 则提供无缝协作的统一工具链。性能方面，LLVM 在处理高级语言特性和跨模块优化时表现更好。
JIT 即时编译¶
- 在程序运行期间动态的将字节码（中间代码）编译成机器码，（这个字节码独立于硬件，是运行在虚拟机上的）
- 程序启动时由虚拟机执行字节码，虚拟机将执行字节码编译成机器码并缓存起来（用于之后再次运行如循环时使用），这种编译是在运行时动态进行的
- 可以利用运行时信息进行检查，动态优化生成更加高效的机器码，并且通过虚拟机具有很好的兼容性
LL 对比 LR¶
| 特性 | LL 解析器 | LR 解析器 |
|---|---|---|
| 分析方法 | 自顶向下 | 自底向上 |
| 推导方式 | 最左推导 | 最右推导的逆序 |
| 扫描方式 | 从左到右扫描输入 | 从左到右扫描输入 |
| 常见类型 | LL(1), 递归下降解析器 | LR(0), SLR(1), LALR(1), LR(1) |
| 实现复杂度 | 实现简单，适合手工编写 | 实现复杂，需要构建解析表和状态机 |
| 处理语法的能力 | 受限于某些语法规则，不能处理左递归 | 能够处理更多种类的语法，包括左递归 |
| 优点 | - 实现简单 - 代码结构与语法规则相对应 |
- 处理复杂语法 - 强大，适用于广泛的语法规则 |
| 缺点 | - 不能处理所有上下文无关文法 - 左递归和某些复杂规则无法处理 |
- 实现和调试较复杂 |
程序设计语言&常识¶
程序设计语言¶
类型机制¶
- 强弱类型：
- 强类型语言：不允许（或少量允许）隐式类型转换，需要进行显式类型转换，如 C++、JAVA、Python
- 弱类型语言：类型规则较为宽松，允许在运行时变量类型变换（隐式转换）如 JS、PHP
- 动态、静态类型：
- 动态类型语言：变量类型在运行时确定：Python、JS
- 静态类型语言：变量类型在编译时确定：JAVA、C++
编程语言执行方式¶
- 编译型语言：在执行前需要经过编译器翻译成机器代码，然后由计算机的处理器直接执行这些机器代码
- 性能高，编译时间较长，具有平台依赖性（机器码是针对特定平台的）
- 如 C、C++、go
- 解释型语言：源代码在执行时逐行翻译成机器代码并立即执行，而不是预先编译成机器代码。
- 开发灵活，不需要编译；运行效率较低，具有平台无关性
- 如 Python、JS、Ruby
- JAVA（JVM 编译型+解释型）：Java 代码先被编译成一种中间代码，然后在 Java 虚拟机上解释执行
- 跨平台（一次编写到处运行），即时编译 JIT（解释）将字节码转化为机器码，性能优于解释型语言
- 结合编译和解释的优点
- 类似的语言还有 C#、PyPy、Nodejs
语法语义语用¶
| 概念 | 定义 | 作用 |
|---|---|---|
| 语法 | 语言的结构规则，规定合法的符号排列 | 确保句子结构正确，编译器和解析器用于语法分析 |
| 语义 | 语言的含义，解释句子的具体意义 | 解释句子的内容和信息，编译器用于语义分析 |
| 语用 | 语言在具体情境中的使用方式和效果 | 研究语言实际应用，考虑上下文对语言理解的影响 |
| ### 面相对象程序设计 | ||
| #### 抽象与封装 | ||
| - 过程式程序设计：过程抽象与封装，数据公开缺乏保护，隐藏过程函数的实现方式 | ||
| - 面相对象程序设计：数据抽象与封装，描述数据能进行哪些操作，只能通过对外接口进行访问 | ||
| ### C++ | ||
| #### 内存分区 | ||
| - 内存 5 大区 | ||
| - 栈区：局部变量、参数、返回地址 | ||
| - 堆区：动态内存分配（生命周期较长） | ||
| - 全局/静态存储区：存储全局变量、静态变量、常亮（程序开始时分配，程序结束时释放）全局变量和静态局部变量放在一块，未初始化的放在另一块。 | ||
| - 文字常量区：常量在统一运行被创建，常量区的内存是只读的，程序结束后由系统释放。 | ||
| - 程序代码区：存放程序的二进制代码，内存由系统管理 | ||
| #### 虚函数与虚继承 | ||
| - 虚函数的工作原理 | ||
| - 虚函数表（vtable）：当一个类中声明了虚函数，编译器会为这个类生成一个虚函数表。这个表是一个函数指针数组，数组中的每个元素都是指向类的虚函数的指针。每个类的虚函数表是唯一的，所有该类的对象都共享同一个虚函数表。 | ||
| - 虚指针（vptr）：当一个类对象被创建时，如果该类中有虚函数，那么编译器会在对象内部添加一个虚指针。这个虚指针指向该类的虚函数表。 | ||
| - 动态绑定：当我们通过基类指针或引用调用虚函数时，编译器会查找指针或引用所指向的对象的虚指针，然后通过虚指针找到对应的虚函数表，最后在虚函数表中查找并调用相应的虚函数。这个过程是在运行时进行的，因此称为动态绑定。 | ||
-  |
||
| - 虚函数表在编译时期创建，为每个有虚函数的类生成一个虚函数表虚函数指针在对象构造时进行初始化，在构造函数的代码中插入设置虚函数表指针的操作 | ||
| - 构造函数一般不定义为虚函数: 虚函数表指针是在创建对象之后才有的，因此不能定义成虚函数。 | ||
| - 析构函数一般定义成虚函数：析构函数定义成虚函数是为了防止内存泄漏 |
- 虚继承的实现原理
- 使用一个虚基类表，虚基类指针
- 虚表中记录了虚基类与本类的偏移地址
- 通过虚基类指针引用公共对象，对象中只保存一份父类的对象，确保了无论通过哪个派生路径访问基类，都是同一个实例。
- 在普通的继承关系中：派生类的构造函数只能通过中间类的构造函数来间接调用基类的构造函数。虚继承关系中派生类可以直接调用，不需要通过中间类
- 虚继承的目的是让某个类做出声明，承诺愿意共享它的基类。其中，这个被共享的基类就称为虚基类。在派生类中都只包含一份虚基类的成员。
构造函数¶
- 拷贝构造函数使用时机：由同类对象创建对象；值传递作为函数参数；对象作为函数返回值
- 构造顺序：基类-成员对象（进入自身构造函数函数体之前进行）-对象自身
- 析构时本身类析构函数的函数体执行完之后，再去调用成员对象类的析构函数。
- 默认拷贝构造函数会调用基类及成员对象的拷贝构造函数；自定义拷贝构造函数会默认调用基类和成员对象的默认构造函数
- 默认赋值会对派生类成员进行赋值，并调用基类的赋值操作；自定义则不会自动调用基类
操作符重载¶
- new delete (必须作为静态的成员函数来重载, 不过 static 可以不写，系统会默认)
- 因为使用 new 时对象还没有被创建，因此只能通过静态成员进行
- 操作符重载本身不支持动态绑定，但是可以通过排在其中调用虚函数来间接实现
JAVA¶
什么是 JVM¶
- Java 虚拟机是一个抽象的计算机，它是 Java 平台的一部分，负责执行 Java 字节码。
- 跨平台性：一次编写到处运行
- 类加载系统：BootStrapClassLoder（本地代码实现，负责加载 JAVA 核心类等）-ExtensionClassLoader-ApplicationClassloaer（加载用户自定义类） 双亲委派机制
- 如果一个类加载器收到了类加载的请求，它首先不会自己去尝试加载这个类，而是把请求委托给父加载器去完成，依次向上。之后，只有当父加载器在它的搜索范围中没有找到所需的类时，子加载器才会尝试自己去加载该类。
- 不同层次的类加载器具有不同优先级，防止用户自定义加载器破坏内置类
- 加载的过程：加载（读取字节码创建 class 对象）；连接（验证、准备（为变量分配内存、设置初始值）、解析（引用替换））；初始化
- 字节码解释：JIT 即时编译
- 内存管理：堆、方法区（类信息、静态变量、常亮等）、虚拟机栈（方法调用、局部变量）、本地方法栈（执行本地 C方法）、程序计数器
- 垃圾回收：
- 发生在新生代的垃圾收集非常频繁。
- 通常在新生代使用复制算法（大批量对象死去）；老生代中使用标记清除或标记整理
- 把年轻代分为了三部分：1 个 Eden 区和 2 个 Survivor 区（分别叫 from 和 to）。默认比例为 8：1：1
- 一般新创建的对象会被分配到Eden 区，在 GC 开始的时候，对象只会存在于 Eden 区和名为“From”的 Survivor 区，紧接着进行 GC，Eden 区中所有存活的对象都会被复制到“To”，而在“From”区中，仍存活的对象会根据他们的年龄值来决定去向。年龄达到一定值的对象会被移动到年老代中，没有达到阈值的对象会被复制到 “To”区域。经过这次 GC 后，Eden 区和 From 区已经被清空。最后“From”和“To”会交换他们的角色。
- 线程管理：提供线程同步和调度机制
- java 运行环境
操作系统¶
什么是虚拟化¶
- 将物理资源（如处理器、内存、磁盘等）转化为更通用更易于使用的虚拟形式。操作系统负责管理分配这些资源，尽可能公平高效
- 虚拟化 cpu：虚拟化 CPU 技术允许多个虚拟机共享同一个物理 CPU。赋予了运行多个程序的能力
- 虚拟化内存：每个进程访问自己的私有虚拟地址空间，操作系统以某种方式映射到机器的物理内存上。进程之间不会相互影响
kernel 是什么¶
- kernel 是指操作系统内核，是操作系统最基础最核心的部分，直接与硬件进行交互，负责管理系统资源
- 资源管理：管理和分配 CPU、内存空间以及其他硬件资源
- 进程管理：创建和进行进程调度
- 设备驱动
- 系统调用
进程与线程¶
- 进程：进程是操作系统进行资源分配和调度的基本单位
- 每个进程都有独立的地址空间，一个进程无法直接访问另一个进程的资源和数据
- 进程间相互隔离，提供了良好的安全性。
- 进程间通信（IPC）相对复杂，开销较大。
- 线程：操作系统能够进行运算调度的最小单位，是进程中的实际运作单位。一个进程可以包含多个线程（更适合进行并行计算）
- 线程间共享进程资源，易于通信和数据共享。
- 相比进程，线程的创建和上下文切换开销更小。
- 共享进程的地址空间和资源，但每个线程有自己的执行序列、栈空间和程序计数器。
如何进行并发控制¶
- 并发控制是指在多线程或多进程环境中，协调资源访问和任务执行，以确保数据的一致性和系统的稳定性。解决资源竞争、死锁等问题
- 互斥：防止多个线程同时访问一个共享资源，可以使用锁、信号量来实现
- 同步：协调多个线程的执行顺序，可以使用条件变量或者屏障
Peterson 互斥算法¶
- 每个人有一个变量（旗子）表示自己是否要使用临界区资源
- 如果要使用临界区资源：
- 举起自己的旗子（先）
- 把写有对方名字的字条贴在临界区上（后）
- 进入观察者模式：
- 如果对方没有举起旗子或者字条上是自己的名字就可以使用临界区资源（手快的先进入）
- 释放：放下旗子
管程¶
- 一种同步构造，用于控制多个线程对共享资源的访问，以保证在任何时刻只有一个线程可以执行临界区的代码。
- 包含：管程的名称；对于管程的共享变量的说明；对管程内数据结构的操作；对数据设置初始值的语句；
什么是生产者消费者模型¶
- 主要由三部分组成：生产者、消费者、缓冲队列
- 生产者（Producer）：
- 负责生成数据，并将数据放入共享缓冲区。
- 如果缓冲区已满，生产者需要等待，直到缓冲区有空间可用。
- 消费者（Consumer）：
- 负责从共享缓冲区取出数据并进行处理。
- 如果缓冲区为空，消费者需要等待，直到缓冲区有数据可用。
读者写者模式¶
- 只能有一个写者进入临界区，但是多个读者可以同时进入（一个读者能进，别的也都应该能进）
- 第一个读者获得锁，最后一个完成的读者释放锁
- 获取读者锁
- 读者进入临界区，保护对读者计数器的访问。
- 增加读者计数器。如果这是第一个读者，则获取写者锁，阻止写者进入。
- 退出临界区，允许其他读者或写者进行操作。
- 释放读者锁
- 读者进入临界区，保护对读者计数器的访问。
- 减少读者计数器。如果这是最后一个读者，则释放写者锁，允许写者进入。
- 退出临界区，允许其他读者或写者进行操作。
避免死锁¶
- 打破锁的必要条件
- 打破条件一：无等待数据结构（通过更强大的硬件原子指令），不许要获取锁，通过原子指令就能实现操作
- 打破条件二：原子取锁，要不取走，要不都不取
- 打破条件三：一个线程加锁失败就放弃所有已经持有的锁，重新开始整个过程
- 打破条件四：任何时刻操作系统中锁有限，给所有锁按照从小到大编号，在获取锁时总是按照从小到大获取
- 通过调度避免锁
- 在每次分配资源时分析分配带来的死锁风险，只有在不产生死锁的情况下，系统才分配资源（线程安全算法）即避免程序进入不安全状态（找不到可以让程序顺利执行的安全序列）
银行家算法的基本过程¶
- 初始化：系统获取每个进程的最大需求矩阵（Max），当前已分配矩阵（Allocation），以及剩余可用资源矩阵（Available）。
- 判断请求合理性：当一个进程请求资源时，首先检查其请求是否超过其声明的最大需求。如果超过，拒绝请求；再判断当前的 available 是否足够进行分配
- 试探性分配：如果请求合理，系统暂时分配资源给该进程，并更新相应的矩阵：
- 将请求的资源从
Available中扣除。 - 增加进程的
Allocation。 - 减少进程的
Need。
- 将请求的资源从
- 安全性检查：系统模拟资源分配后的状态，检查是否存在一个安全序列
- 找到一个
Need小于或等于Available的进程。 - 假定该进程获得其需要的所有资源并完成执行，释放其资源，更新
Available。 - 重复上述步骤，直到所有进程都能满足需求，或者找不到符合条件的进程为止。
- 找到一个
- 决策：如果能找到安全序列，说明分配请求不会导致死锁，正式分配资源；否则，恢复之前的状态，拒绝请求。
（设备）控制器和通道的区别¶
- 设备控制器是管理和控制外围设备的硬件组件，负责设备与内存之间的数据传输。它解释和执行 CPU 的命令，如读写和状态查询命令，并在操作完成或发生错误时生成中断信号通知 CPU。
- 通道是一种高级硬件组件或专用处理器，用于管理复杂的 I/O 操作。它能够独立于 CPU 执行复杂的 I/O 任务，支持多步操作和并行处理。通道可以运行预定义的 I/O 指令序列，并在任务完成后通过中断通知 CPU。
- 设备控制器和通道的主要区别在于复杂性和 CPU 干预程度。设备控制器通常用于单一设备的基本 I/O 操作，需要较多的 CPU 干预，而通道可以处理更复杂的 I/O 任务，支持并行操作，减少 CPU 的干预。通道具有更高的智能性和独立性，能够显著提高系统的 I/O 性能。
并行与并发的区别¶
- 并行：同时执行多个任务。在硬件上，这意味着多个处理器或多核处理器同时处理不同的任务或同一个任务的不同部分
- 用于处理高性计算问题
- 并发：同一时间段内管理和执行多个任务。虽然这些任务不一定同时执行，但它们在同一时间段内交替进行，给用户的感觉是同时进行。
- 如通过时间分片技术，使多个任务交替执行，从而在宏观上看似同时进行。主要依赖于操作系统和调度算法
- 用于处理有大量阻塞操作如 IO 的多个程序
操作系统中的文件组织结构¶
- 文件组织有 (文件的逻辑结构)：有结构的记录文件和无结构的流文件
- 逻辑结构：顺序文件，索引文件，索引顺序文件
- 物理结构：顺序结构，链接结构，索引结构
- 外存文件的空闲空间管理：空闲表和空闲链表，位示图，成组链接法
进程的状态模型¶
系统调用与库函数的区别¶
系统调用是程序与操作系统内核之间的接口，允许用户程序请求操作系统执行特定任务，如文件操作、进程管理和内存管理。系统调用需要从用户态切换到内核态，涉及上下文切换，因此开销较大。 库函数是由编程语言的标准库或第三方库提供的函数，封装了常用功能，便于程序员调用。库函数通常在用户态执行，不涉及内核态切换，因此开销较小。它们通常是对底层系统调用的封装，提供更高层次的接口。 系统调用直接与操作系统内核交互，执行特定的低级任务，涉及用户态到内核态的切换，开销较大；库函数则在用户态执行，封装了系统调用和其他常用功能，提供更高层次的接口，开销较小，便于程序员使用。
死锁的条件及处理方式¶
- 必要条件：互斥条件、请求和保持、不剥夺、循环等待
- 预防死锁：破坏死锁的必要条件（限制太严格，降低效率）
- 避免死锁：资源动态分配过程中防止系统进入不安全状态（如银行家算发烧）
- 检测和解除死锁：用于检查运行过程中是否发生了死锁
数据库¶
ACID¶
- 原子性、一致性、隔离性、持久性
数据库和操作系统文件系统区别¶
| 项目 | 数据库 | 文件系统 |
|---|---|---|
| 目标 | 管理和查询结构化数据 | 存储和管理文件和目录 |
| 数据组织 | 表格结构（行和列） | 树状结构（文件和目录） |
| 功能 | 支持事务（ACID）、复杂查询、并发控制、数据备份 | 基本文件操作（读写删改）、权限管理、空间管理 |
| 使用场景 | 业务系统、数据分析、应用开发 | 操作系统、文件存储、文件共享 |
| 总结 | 用于复杂数据管理和查询，支持事务和并发 | 用于简单文件存储和管理，支持基本文件操作和权限控制 |
| ## 计算机网络 | ||
| ### IPV 6 与 IPV 4 的区别 | ||
| - 出现原因：IPv 4 地址空间耗尽，NAT 复杂了路由器和网络配置 | ||
| - 区别 | ||
| - 更大的地址空间 | ||
| - 支持无状态地址自动配置（不需要 DHCP） | ||
| - 无 NAT | ||
| - 内置 IPSec 支持 | ||
| - 简化的包头：使用扩展包头（如分片头、esp 头等），通过 nextheader 字段将包头串成一个链 | ||
| - 改进多播支持 | ||
| - 优先级处理：（IPV 4 使用 ToS 字段）过识别、优化和管理具有相同特征的数据包流，以提升传输效率和服务质量 |
| 特性 | IPv4 | IPv6 |
|---|---|---|
| 版本号 | 4 | 6 |
| 头部长度 | 可变，最小20字节 | 固定40字节 |
| 地址长度 | 32位 | 128位 |
| 服务类型 | Type of Service（8位） | Traffic Class（8位） |
| 总长度/负载长度 | 总长度（16位），包括头部和数据 | 负载长度（16位），仅数据部分 |
| 标识、标志、片偏移 | 用于分片和重组 | 没有这些字段，分片在扩展头部中处理 |
| TTL/Hop Limit | TTL（8位），限制数据报生存时间 | Hop Limit（8位），限制数据包跳数 |
| 协议/下一个头部 | Protocol（8位），指示上层协议类型 | Next Header（8位），指示下一个头部类型 |
| 头部校验和 | 有头部校验和（16位） | 没有头部校验和，依赖更高层和链路层的校验和 |
| 选项 | 有可选的选项字段，长度可变 | 没有选项字段，扩展功能通过扩展头部实现 |
| 流标签 | 无 | Flow Label（20位），用于标识数据流 |
| ### 计算机网络分层设计的优点 | ||
| 1. 简化设计和实现：分层将复杂的网络功能分解为多个相对简单的、独立的层次，每一层只需关注其特定的功能和服务，从而简化了设计和实现过程。 | ||
| 2. 标准化和互操作性：各层之间定义明确的接口和协议，使得不同厂商的设备和软件能够相互通信和协作，促进了标准化和互操作性。 | ||
| 3. 模块化和可维护性：每一层的实现可以独立开发和更新，不会影响其他层。这种模块化设计提高了系统的可维护性和灵活性。 | ||
| 4. 故障隔离和调试：分层设计使得故障隔离和调试更加容易。通过逐层检查，可以快速定位和解决问题，提高网络维护效率。 | ||
| 5. 灵活性和扩展性：分层结构允许在不改变整体架构的情况下，对某一层进行扩展和优化，提供了更大的灵活性和扩展能力。 | ||
| ### 对比 FTP 和 HTTP | ||
| - FTP：文件传输协议 | ||
| - HTTP：超文本传输协议 |
| 特性 | FTP | HTTP |
|---|---|---|
| 设计目的 | 专为文件传输设计 | 专为传输超文本和网页内容设计 |
| 连接方式 | 使用控制连接和数据连接 | 使用单一连接 |
| 传输模式 | 支持主动模式和被动模式 | 仅支持请求-响应模式 |
| 数据传输 | 二进制和ASCII模式 | 基于二进制传输 |
| 端口 | 控制连接使用端口21，数据连接使用端口20或随机端口 | 默认使用端口80（HTTP）或443（HTTPS） |
| 状态管理 | 需要维护会话状态 | 无状态协议，每个请求独立处理 |
| 安全性 | FTP传输时数据不加密（FTPS、SFTP提供加密） | HTTPS使用SSL/TLS加密数据传输 |
| 使用场景 | 文件上传和下载 | 网页浏览、API请求、文件下载 |
| 命令控制 | 使用FTP命令控制文件操作 | 通过HTTP方法（GET、POST、PUT、DELETE）操作资源 |
| 支持断点续传 | 支持 | 支持（需要客户端和服务器共同支持） |
| ## 数据结构与算法 | ||
| ### 常见算法的复杂度 | ||
| -  |
| 算法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| Huffman | O(n log n) | O(n) | n是字符集的大小，使用优先队列实现 |
| Dijkstra | |||
| - 数组实现 | O (V^2+E) | O(V) | V 是顶点数 |
| - 二叉堆实现 | O((V + E) log V) | O(V) | V是顶点数，E是边数 |
| Prim | |||
| - 数组实现 | O (V^2+E) | O(V) | V 是顶点数 |
| - 二叉堆实现 | O((V + E) log V) | O(V) | V是顶点数，E是边数 |
| Kruskal | O(E log E) | O(E) | 使用并查集 |
| Floyd-Warshall | O(V^3) | O(V^2) | 适用于所有顶点对的最短路径 |
| Bellman-Ford | O(VE) | O(V) | 适用于含有负权边的最短路径 |
| KMP | O(n + m) | O(m) | n是文本长度，m是模式长度 |
| - dirkstra 的时间复杂度可以分为三部分：V 次查找最小值、V 次插入元素、E 次删除（修改元素） | |||
| ### 抽象数据类型 | |||
| - 抽象数据类型是指一组数据及其相关操作的数学模型，它抽象了数据结构的实现细节，强调数据及其操作的逻辑行为，而不关心其具体实现方式。 | |||
| - 包含数据元素、数据的关系和相关的操作 | |||
| - 具有抽象与封装的特点 | |||
| ## 杂项 | |||
| ### 图灵机 | |||
| - 一种抽象计算模型，用于形式化描述计算过程和计算能力。 | |||
| - 图灵机的组成部分： | |||
| 1. 无限长的纸带：纸带分为一个个单元格，每个单元格可以存放一个符号 | |||
| 2. 读写头：读写头可以在纸带上移动，每次可以读取或写入一个符号，并根据读取的符号和当前状态决定接下来的操作。 | |||
| 3. 状态寄存器：记录图灵机当前的状态。 | |||
| 4. 有限的状态集合和转移函数：转移函数决定了图灵机在每个状态下，根据读取到的符号应执行的操作。 | |||
| - 图灵机的工作原理： | |||
| - 图灵机根据当前状态和读写头读取到的符号，通过转移函数决定接下来要执行的操作。 | |||
| - 它可以改变当前单元格中的符号，移动读写头到左边或右边的单元格，并转移到一个新的状态。 | |||
| - 图灵机的计算过程可以无限进行，直到达到一个接受状态（或拒绝状态）或进入一个无限循环。 | |||
| - 图灵机停机问题：给定一个图灵机和一个输入，判断该图灵机在这输入上是否会最终停机（即，经过有限步操作后停止运行）。 | |||
| - 图灵机停机问题是不可判定的，也就是说，不存在一个通用的算法可以判断所有图灵机及其输入是否会停机 | |||
| - 展示了有些问题是无法通过计算机程序解决的。 | |||
| ### 图灵测试 | |||
| - 用于判断机器是否具有人类智能。其核心思想是，如果一个人类测试者通过与人类和机器分别对话，无法可靠地区分出哪一方是机器，那么该机器就被认为通过了图灵测试，展示了类似于人类的智能水平。 | |||
| ### 平台无关性 | |||
| - 软件系统或编程语言能够在不同的硬件平台和操作系统上运行，而无需进行修改或重新编译。 | |||
| - 编程语言的平台无关性：JAVA 字节码通过 JVM 实现平台无关运行 | |||
| - 应用程序的平台无关性：Qt 框架等提供跨平台开发环境 | |||
| - Web 技术：借助浏览器提供的平台无关运行环境天然支持平台无关性 |