Linear Time

定义 Definition

“线性时间”：在算法分析中，指运行时间（或步骤数）随输入规模 n 成正比增长，通常记作 **O(n)**。

例句 Examples

The algorithm checks each item once, so it runs in linear time.
这个算法把每个元素检查一遍，因此它是线性时间。

With a hash set, we can remove duplicates in linear time for large datasets.
借助哈希集合，我们可以在处理大型数据集时用线性时间去重。

发音 Pronunciation (IPA)

/ˈlɪniər taɪm/

词源 Etymology

linear 来自拉丁语 linearis（“线的、成直线的”），源于 linea（“线”）；time 来自古英语 tīma（“时间、时刻”）。在计算机科学语境中，“linear time”借用“直线式增长”的形象来描述耗时随规模均匀增加的关系。

相关词 Related Words

• Algorithm
• Complexity
• Big-O Notation
• Constant Time
• Logarithmic Time
• Quadratic Time
• Linearithmic Time
• Runtime

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：多处讨论 “linear time / O(n)” 的算法与界限
• The Art of Computer Programming（Donald E. Knuth）：在算法效率与复杂度讨论中使用 “linear time”
• Algorithms（Robert Sedgewick & Kevin Wayne）：在排序、查找、图算法分析中频繁出现 “linear time”