lowcode-engine 如何配置渲染唯一标识 key 避免同类组件切换时表单值串值
2026/9/14 9:57:00
一、基本查找算法对比
| 算法 | 时间复杂度 | 空间复杂度 | 适用条件 | 平均查找长度（ASL）公式 | 特点 |
|---|---|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无序/有序线性表 | 成功：(n+1)/2 失败：n+1 | 可用哨兵优化 |
| 折半查找 | O(log n) | O(1) | 有序顺序表 | 成功：向下取整[log₂(n)] + 1 | 需随机访问，链表不可用 |
| 分块查找 | O(√n)（理想块大小） | O(1) | 块间有序+块内无序 | 索引顺序+块内顺序：(b+1)/2+(s+1)/2 | 动态索引效率高 |
- 顺序查找：
- 最好：表头开始，O(1)
- 最坏：表尾开始，O(n)
- 平均：(n+1) / 2，所以是O(n)
- 折半查找：
- 最大比较次数（二叉搜索树）=向下取整[log₂(n)] + 1（例如：一个长度16的顺序表元素按关键字有序排列，找一个表中不存在的元素则key之间比较次数最多是：5次）。
- 最少比较次数：1次。
- 🚩不适用场景：链表（因为无法随机访问）。例：有序链表，无序数组，有序静态链表，无序静态链表。
- 折半查找判定树：观察其左倾，右倾，一棵树在查找时会固定要么左要么右，不会找到一半改变方向。
- 二叉搜索树保证有序
- 分块查找：
- 索引表必须有序
二、分块查找➡平均查找长度ASL = 索引查找 + 块内查找
1. 性能公式对比
假设长n的表，分成b块，每块里面有s条
| 索引查找 | 块内查找 | ASL公式 | 示例（n=100, b=10, s=10） |
|---|---|---|---|
| 顺序查找 | 顺序查找 | (b+1)/2 + (s+1)/2 | 5.5 + 5.5 = 11 |
| 折半查找 | 顺序查找 | 向下取整[log₂(b)] + 1 + (s+1)/2 | 4 + 5.5 = 9.5 |
| 最佳块大小 | - | s=√n 时 ASL最小≈√n | √100=10 |
2. 块划分原则
- 块间有序：第i块最大关键字 < 第i+1块最小关键字
- 块内无序：块内无需排序，节省维护成本
- 索引表结构：存储每块的最大关键字和起始地址
3. ASL计算误区
- 失败查找长度 ≠ 成功查找长度
- 分块查找：需分开计算索引和块内查找