线性对数

线性对数（或称对数线性、拟线性、超线性）的形式为${\displaystyle n\log <!--\; \; -->n}$，是线性函数及对数函数相乘的结果，在计算复杂度理论中常用线性对数来描述一些算法的时间复杂度。

若以渐进符号表示，线性对数${\displaystyle n\log <!--\; \; -->n}$的复杂度为${\displaystyle \mathrm{\omega <!--\; \omega \; -->}(n),o(n^2),\mathrm{\Theta <!--\; \Theta \; -->}(n\log <!--\; \; -->n)}$。线性对数成长的比线性函数${\displaystyle n}$快，但比平方函数${\displaystyle n^2}$慢。

许多算法的时间复杂度为${\displaystyle \mathrm{O}(n\log <!--\; \; -->n)}$，例如：