Linear Scan

释义 Definition

线性扫描：按顺序从头到尾逐个检查元素/位置的一种方法或过程。常见于计算机科学中，例如数组遍历、顺序查找、文本处理，或“线性扫描寄存器分配”（linear scan register allocation）。通常时间复杂度为 **O(n)**。

发音 Pronunciation (IPA)

/lnir skn/

例句 Examples

She did a linear scan of the list to find the first empty slot.
她对列表做了线性扫描，找到了第一个空位。

Instead of using an index, the program performs a linear scan through the log file, which is simple but can be slow when the file is huge.
程序没有使用索引，而是对日志文件进行线性扫描；这种做法简单，但当文件非常大时可能会很慢。

词源 Etymology

linear 源自拉丁语 linea（“线、线条”），引申为“沿着一条线、按顺序”。scan 来自拉丁语 scandere（“攀登、逐步走过”），后来在英语中发展出“快速查看/细看、逐行检查”的含义。组合成 linear scan，强调“按顺序逐个检查”的过程。

相关词 Related Words

• Sequential Search
• Iteration
• Traversal
• Loop
• Index
• Binary Search
• Complexity
• Register Allocation

文学与著作 Literary Works

• Modern Compiler Implementation in Java（Andrew W. Appel）：讨论编译器后端时常提到扫描类算法与寄存器分配相关概念（包括线性扫描分配的语境）。
• Engineering a Compiler（Keith D. Cooper, Linda Torczon）：在寄存器分配与优化章节中涉及线性扫描等实用算法思想。
• 论文 Linear Scan Register Allocation（Massimiliano Poletto, Vivek Sarkar）：以“linear scan”作为核心术语与方法名称，在编译器领域引用广泛。