Subquadratic

释义 (Definition)

subquadratic（多用于计算机科学/数学）指“次二次的；低于二次方增长的”。常见于时间复杂度或空间复杂度：增长速度 比 (n^2) 更慢（例如 (n^{1.9})、(n\log n)、(n\sqrt n) 等都可称为 subquadratic）。在不同语境下也可能泛指“低于平方级别”的规模或代价。

发音 (Pronunciation, IPA)

/ˌsʌbkwɑːˈdrætɪk/

例句 (Examples)

A subquadratic algorithm can handle much larger inputs.
次二次算法可以处理大得多的输入规模。

Researchers proposed a subquadratic-time method for comparing long strings, improving performance on large datasets.
研究人员提出了一种用于比较长字符串的次二次时间方法，从而提升了在大规模数据集上的性能。

词源 (Etymology)

由 **sub-**（拉丁语前缀，意为“在……之下/低于”）+ quadratic（“二次的/平方的”，源自 quadratus “方形的/成方的”）构成，字面意思就是“低于二次（平方）级别的”。

相关词 (Related Words)

• Algorithm
• Complexity
• Quadratic
• Sublinear
• Near-Linear
• Superlinear
• Polynomial

文献与作品用例 (Literary / Notable Works)

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常简称 CLRS）：在讨论算法复杂度时常出现与“subquadratic”相关的表述与对比（如与 quadratic 的差别）。
• The Design and Analysis of Computer Algorithms（Aho, Hopcroft, Ullman）：在算法分析语境中会涉及“低于二次时间”的算法类别。
• 计算机科学研究论文中常见：关于字符串匹配、编辑距离、最近点对、矩阵乘法、图算法等主题，常以“subquadratic time”作为重要性能目标或突破点。