Linearithmic Time

释义 Definition

线性对数时间；准线性时间：指算法的时间复杂度大致为 **O(n log n)**，增长速度介于线性时间 O(n) 和二次时间 O(n²) 之间，常见于高效排序与分治算法（如归并排序、堆排序）。

发音 Pronunciation (IPA)

/ˌlɪn.i.əˈrɪð.mɪk taɪm/

例句 Examples

Sorting the list with merge sort usually takes linearithmic time.
用归并排序对这个列表排序通常需要线性对数时间。

For very large datasets, an O(n log n) algorithm often scales well compared with quadratic approaches, making linearithmic time a practical target in system design.
对超大数据集而言，O(n log n) 的算法通常比二次方法更能扩展，因此在系统设计中把线性对数时间作为目标往往更实际。

词源 Etymology

linearithmic 是一个混成词（portmanteau），由 linear（线性的） 与 logarithmic（对数的） 组合而来，用来直观表达“线性 × 对数”这种常见的复杂度形式；再加上 time 表示时间复杂度语境。

相关词 Related Words

• Logarithmic
• Linear
• Quasilinear
• Polynomial
• Complexity
• Merge Sort
• Heap Sort
• Divide and Conquer

文献与作品 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，俗称 CLRS）——在排序、递归式与渐进分析中大量讨论 **O(n log n)**（即 linearithmic time）。
• The Art of Computer Programming（Donald E. Knuth）——在算法分析与排序相关章节中常出现线性对数级别的讨论。
• Algorithms（Robert Sedgewick & Kevin Wayne）——讲解归并排序、堆排序等时频繁使用“linearithmic time / n log n time”表述。