線性對數

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

若以漸進符號表示，線性對數${\displaystyle n\log n}$的複雜度為${\displaystyle \omega (n),o(n^{2}),\Theta (n\log n)\!}$。線性對數成長的比線性函數${\displaystyle n}$快，但比平方函數${\displaystyle n^{2}}$慢。

參見

許多演算法的時間複雜度為${\displaystyle \mathrm {O} (n\log n)\!}$ ，例如：

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