空间复杂度

原地排序

type: concept tags: [排序算法特性, 空间复杂度] created: 2026-05-06 updated: 2026-05-06原地排序（In-place Sort）定义原地排序是指仅需 O(1) 额外空间（不算输入数组本身）的排序算法。算法通过直接修改输入数组来完成排序，不需要额外的数组来存储中间结果。核心特性| 特性 | 说明 | |------|------| | 空间复杂度 | O(1)（仅需常数级额外变量） | | 实现方式 | 通过元素交换或移动，直接在原数组上操作 | | 优点 | 节省内存，适合内存受限场景 | | 缺点 | 实现可能较复杂，某些算法（如堆排序）实际性能可能不如预期 |常见原地排序算法| 算法 | 时间复杂度（平均） | 稳定性 | 说明 | |------|-------------------|--------|------| | 选择排序 | O(n²)

哈希表

type: concept tags:哈希表数据结构HashMap键值对哈希函数 created: 2026-05-03 updated: 2026-05-03哈希表（Hash Table）定义哈希表（Hash Table，也称散列表）是一种基于哈希函数实现的数据结构，能够在平均 O(1) 时间内完成插入、删除和查找操作。核心思想：通过哈希函数将键（key）映射到数组的某个索引位置，直接访问该位置获取数据。基本原理键值对 (key, value) │ ▼ 哈希函数 hash(key) → 数组索引 index │ ▼ 数组 table[index] = value伪码表示put(key, value): index = hash(key)

基数排序

type: concept tags: [排序算法, 非比较排序, 稳定排序, 计数排序] created: 2026-05-09 updated: 2026-05-09基数排序（Radix Sort）基数排序按数字位依次排序，依赖稳定排序保持低位排序结果，是计数排序在多位整数上的扩展应用。定义基数排序（Radix Sort）是一种非比较排序算法。它将待排序元素按“位”拆解，从低位到高位依次进行稳定排序，最终得到整体有序结果。这里的“基数”（radix）指进制。例如十进制整数的基数是 10，二进制整数的基数是 2。核心特性| 特性 | 说明 | |------|------| | 排序类型 | 非比较排序 | | 基础子过程 | 通常使用稳定版 [[计数排序]] | | 稳定性要求 | 每一位排序都必须稳定 | | 数据要求 | 整数，或可以映射成整数的值 | | 时间复杂度 | O(d * (n + k))，d

大O表示法

type: concept tags: [算法, 复杂度分析, 数学记号, 基础理论] created: 2026-05-06 updated: 2026-05-06大O表示法描述算法复杂度渐进上界的数学记号，用于简洁表达算法效率随输入规模增长的趋势。定义Big O 记号的数学定义：$O(g(n))$ = { $f(n)$: 存在正常量 $c$ 和 $n_0$ ，使得对所有 $n ≥ n_0$ ，有 $0 ≤ f(n) ≤ c*g(n)$ }$O$（大写字母 O）代表一个函数集合。$O(n^2)$ 代表由 $g(n) = n^2$ 派生的函数集合；说算法复杂度为 $O(n^2)$ 意味着描述该算法的复杂度函数属于此集合。核心特性1. 只保留增长速率最快的项乘法和加法中的常数因子可忽略：| 原式 | 简化后

排序算法

type: concept tags:排序算法算法基础时间复杂度 created: 2026-05-05 updated: 2026-05-09排序算法 (Sorting Algorithm)将一组数据按照特定顺序（如从小到大）排列的算法集合，是计算机科学中最基础的算法类别之一。定义排序算法是指将一组无序数据按照特定比较规则（通常是数值大小或字典序）重新排列成有序序列的算法。核心评估指标根据[[排序算法的关键指标]]，评估排序算法需要从三个维度综合考虑：| 指标 | 说明 | | ---------- | ------------------ | | 时间复杂度

时间复杂度

type: concept tags: [算法, 复杂度分析, 基础理论] created: 2026-05-02 updated: 2026-05-02时间复杂度描述算法执行时间随输入规模增长的渐近趋势，是评估算法效率的核心指标之一，常用大O表示法。核心定义时间复杂度：算法执行时间随输入规模 $n$ 增长的渐近上界，记为 $O(f(n))$，忽略常数项和低阶项均摊时间复杂度：对多次操作的整体时间复杂度分析，适用于单次操作开销大但出现频率极低的场景（如动态数组扩容）大O表示法特性本文补充的两个关键特性：只保留增长速率最快的项：O(2N + 100) = O(N)，O(N³ + 999N²) = O(N³)注意：指数中的常数不能消，O(2^(2N)) = O(4^N)大O表示法表示上界：O(N) 算法也可说成 O(N²)，只是上界不够"紧"实际分析时数量级正确（线性/指数/对数级）即可常见复杂度层级| 复杂度 | 层级 | 说明 | |--------|------|------| | O(1) | 常数级 | 哈希表查询 | | O(logN) | 对数级 | 二分查找、平衡树 | |

滑动窗口

type: concept tags: [算法技巧, 双指针, 子数组, 子串] created: 2026-05-05 updated: 2026-05-05滑动窗口（Sliding Window）通过左右指针维护一个窗口区间，在 O(N) 时间内解决子数组/子串问题的算法技巧。定义滑动窗口是一种基于快慢双指针的算法技巧，通过维护一个 [left, right) 左闭右开的窗口区间，不断滑动窗口来寻找满足特定条件的最优子数组或子串。它将暴力解法的 O(N²) 时间复杂度优化为 O(N)。核心特性| 特性 | 说明 | |------|------| | 本质 | 快慢双指针，一快一慢前后相随，中间部分即窗口 | | 时间复杂度 | O(N)，每个元素进出窗口各一次 | | 空间复杂度 | O(k)，k 为窗口内不同元素的数量 | | 适用问题 | 寻找满足某条件的最长/最短子数组（子串） | | 区间定义 |

稳定排序

type: concept tags: [排序算法, 稳定性, 算法特性] created: 2026-05-05 updated: 2026-05-09稳定排序 (Stable Sort)排序算法的一种特性：相等元素的相对顺序在排序后保持不变。定义稳定排序（Stable Sort） 是指：如果两个元素比较相等（或关键字相同），那么在排序前和排序后，这两个元素的相对位置保持不变。例如：对 (value, originalIndex) 对进行排序，初始为 [(5,0), (2,1), (5,2), (1,3)]，稳定排序后结果为 [(1,3), (2,1), (5,0), (5,2)]，两个值为 5 的元素保持了原有的相对顺序（index 0 在 index 2 前面）。核心特性| 特性 | 说明 | |------|------| | 稳定性 | 相等元素保持原有相对顺序 | | 适用场景 | 需要保持原始顺序的多关键字排序

计数排序

type: concept tags: [排序算法, 非比较排序, 线性时间排序] created: 2026-05-05 updated: 2026-05-09计数排序 (Counting Sort)一种非比较排序算法，通过统计元素出现次数实现 O(n + k) 时间复杂度排序，适合元素值范围不大的整数排序场景。定义计数排序（Counting Sort）是一种非比较排序算法，其核心思想是：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。与比较排序（如快速排序、归并排序）不同，计数排序不通过比较元素大小来决定顺序，而是利用元素值作为索引直接定位。核心特性| 特性 | 说明 | |------|------| | 排序类型 | 非比较排序 | | 时间复杂度 | O(n + k)，k = max - min + 1（元素值范围） | | 空间复杂度 | O(n + k) | |

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

log

Harness Engineering - 操作日志本页面记录所有 Claude 的操作记录，仅追加，不修改历史记录[2026-05-02] init | 初始化仓库结构创建 raw/ 目录结构（articles, papers, images）创建 wiki/ 目录结构（entities, concepts, summaries, comparison）创建 wiki/index.md 索引页创建 wiki/log.md 操作日志仓库初始化完成[2026-05-02] ingest | 时间空间复杂度入门保存原始内容到 raw/articles/复杂度分析基础.md创建摘要页 wiki/summaries/2026-05-02 时间空间复杂度入门.md侧重：复杂度分析的实用方法（Big O 简化估算技巧）更新 wiki/index.md：摘要页数量 0→1注意：labuladong 实体和复杂度概念首次出现，暂不创建独立页（需 ≥2 篇来源）[2026-05-02] ingest | 数组基础（labuladong）提取网页内容（defuddle）并创建摘要页 wiki/summaries/2026-05-02 数组基础.md创建实体页

排序算法的关键指标

type: summary tags:排序算法算法基础稳定性 created: 2026-05-05 updated: 2026-05-05排序算法的关键指标[[raw/articles/2026/05/排序基础]]一句话总结介绍排序算法的三个核心评估指标：时空复杂度、排序稳定性和是否原地排序，为后续学习具体排序算法打下基础。核心要点1. 时空复杂度排序算法的效率由时间复杂度和空间复杂度共同衡量。时间复杂度描述算法执行时间随输入规模增长的趋势，空间复杂度描述算法占用额外存储空间的情况。复杂度越低，算法性能越好。2. 排序稳定性稳定排序的定义：对于序列中的相同元素，如果排序之后它们的相对位置没有发生改变，则称该排序算法为「稳定排序」，反之则为「不稳定排序」。实际意义：对于简单 int 数组排序，稳定性意义不大对于复杂数据结构（如订单数据），稳定排序能保持多字段排序的层次性实例说明： 假设已有按日期排序的订单数据，现需按用户 ID 排序：使用稳定排序：相同用户 ID 的订单仍按日期有序排列使用不稳定排序：相同用户 ID 的订单相对位置可能变化，日期有序性丧失3. 是否原地排序原地排序定义：排序过程中不需要额外的辅助空间，只需要常数级别的额外空间，直接操作原数组进行排序。区别示例：// 非原地排序：需要 O(N) 额外空间 void sort(int[] nums) { int[] tmp = new int[nums.length]; // 辅助数组 // 对 nums 进行排序

时间空间复杂度入门

type: summary tags: [算法, 复杂度分析, 时间复杂度, 空间复杂度] created: 2026-05-02 updated: 2026-05-02时间空间复杂度入门 - 实用分析方法[[raw/articles/2026/05/复杂度分析基础]]来源：labuladong 算法网站 侧重：复杂度分析的实用方法（简化估算技巧）核心要点：实用估算方法1. 大O表示法简化原则关键规则：忽略常数项和低增长项，只保留最高增长项| 原始表达式 | 简化后 | |-----------|--------| | $O(2n^2 + 3n + 1)$ | $O(n^2)$ | | $O(1000n + 1000)$ | $O(n)$ | | $O(5\log n + 10)$ | $O(\log n)$ |2. 时间复杂度快速估算实用技巧：大部分情况下，看 for

滑动窗口框架

type: summary tags: [滑动窗口, 算法框架, 双指针, LeetCode] created: 2026-05-05 updated: 2026-05-05滑动窗口算法框架[[raw/articles/2026/05/滑动窗口框架.md]]一句话总结提供滑动窗口算法的通用代码框架，通过左右指针维护窗口，将子数组/子串问题的时间复杂度从 O(N²) 优化到 O(N)。核心要点1. 滑动窗口基本原理滑动窗口是快慢双指针的应用，维护一个 [left, right) 左闭右开区间作为窗口，通过扩大和缩小窗口寻找满足条件的最优解。核心思路：第1步：移动 right 扩大窗口，直到满足条件（寻找可行解）第2步：移动 left 缩小窗口，优化结果（优化可行解）重复上述过程，直到 right 到达尽头时间复杂度 O(N) 的原因：left 和 right 指针只增不减，不回退每个元素只进入窗口一次，离开窗口一次嵌套 while 循环的总执行次数与 N 成正比（均摊分析）2. 通用代码框架// 滑动窗口算法伪码框架 void slidingWindow(String s) { // 用合适的数据结构记录窗口中的数据

计数排序-总结

type: summary tags: [排序算法, 计数排序, 非比较排序] created: 2026-05-05 updated: 2026-05-05计数排序[[raw/articles/2026/05/计数排序]]一句话总结计数排序通过统计每种元素出现的次数来推算排序后位置，时间空间复杂度均为 O(n + max - min)，是一种非比较排序算法。核心要点1. 基本原理计数排序的核心思想是：统计每种元素出现的次数，进而推算出每个元素在排序后数组中的索引位置，最终完成排序。需要将元素的值作为 count 数组的索引才能计数仅关心元素出现次数，不关心相同元素的相对位置 → 不稳定排序适合元素值范围不大的场景2. 时间空间复杂度| 指标 | 复杂度 | 说明 | |------|--------|------| | 时间复杂度 | O(n + max - min) | n 是数组长度，max - min 是元素值范围 | | 空间复杂度 |

选择排序-总结

type: summary tags:排序算法选择排序时间复杂度稳定排序 created: 2026-05-05 updated: 2026-05-05选择排序[[raw/articles/2026/05/选择排序]]一句话总结选择排序是最简单朴素的排序算法，时间复杂度 O(n²)，不是稳定排序，其他基础排序算法都是基于选择排序的优化。核心要点1. 算法思路先遍历数组找到最小值，与第一个元素交换；再遍历剩余部分找到次小值，与第二个元素交换；以此类推直到整个数组有序。2. 时间复杂度与优化尝试时间复杂度：O(n²)，嵌套循环执行 n²/2 次特点：即使数组已有序，仍执行相同次数，原始数据有序度不影响时间复杂度优化尝试：尝试用 suffixMin 数组预计算后缀最小值，但因交换操作导致 nums 变化，预计算失效，无法优化3. 排序稳定性不是稳定排序：交换操作会打乱相同元素的相对位置原因：第一次寻找最小值时就可能交换，破坏相同元素的原始顺序优化思考：作者提出思考方向，后续排序算法会尝试解决基本原理选择排序的核心：每次选择未排序部分的最小值，放到已排序部分的末尾。void sort(int[] nums) { int n = nums.length; int sortedIndex = 0; // 已排序/未排序分割线 while (sortedIndex <