線性對數

線性對數〔或稱對數線性、擬線性、超線性〕的形式為 n · log n ，是線性函數及對數函數相乘的結果，在計算複雜度理論中常用線性對數來描述一些演算法的時間複雜度。

若以漸進符號表示，線性對數 n · log n的複雜度為 ω(n), o(n²), 及 Θ(n · log n)。線性對數成長的比線性函數 n 快，但比平方函數 n² 慢。

許多演算法的時間複雜度為O(n · log n )，例如：

• 快速排序法的一般情形
• 快速傅利葉變換

这是一个与数学相关的小作品，您可以帮助维库扩充其内容。