Sublinear

释义 Definition

sublinear（形容词）：次线性的；指增长速度低于线性（例如随输入规模增大，但增长得比 (n) 更慢，如 (\log n)、(\sqrt{n}) 等）。常用于数学、统计学与计算机科学（如“次线性时间算法”）。

发音 Pronunciation (IPA)

/sʌbˈlɪniər/

例句 Examples

A sublinear increase means the cost grows slowly as the input gets larger.
次线性增长表示随着输入变大，成本增长得很慢。

The paper proposes a sublinear-time algorithm that estimates the answer without scanning the entire dataset.
这篇论文提出了一种次线性时间算法，可以在不遍历整个数据集的情况下估计答案。

词源 Etymology

由前缀 **sub-**（“在……之下、低于”）+ linear（“线性的”）组成，字面意思是“低于线性的”。该词常见于描述“增长率/复杂度”时，强调其增长速度比线性关系更慢。

相关词 Related Words

• Linear
• Nonlinear
• Logarithmic
• Polynomial
• Superlinear
• Subquadratic
• Asymptotic
• Complexity

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：讨论时间复杂度时常涉及“sublinear time”的概念。
• Randomized Algorithms（Motwani & Raghavan，《随机算法》）：在子线性估计、抽样与近似算法语境中使用该术语。
• The Probabilistic Method（Alon & Spencer，《概率方法》）：相关章节常谈到依赖随机化与抽样实现的次线性（或近似）方法。