线性对数_线性函数及对数函数相乘的结果

线性对数

线性函数及对数函数相乘的结果

线性对数或称对数线性、拟线性、超线性，形式为 n · log n ，是线性函数及对数函数相乘的结果，在计算复杂度理论中常用线性对数来描述一些算法的时间复杂度。

简介

若以渐进符号表示，线性对数 n · log n的复杂度为 ω(n), o(n2), 及 Θ(n · log n)。线性对数成长的比线性函数 n 快，但比平方函数 n2 慢。

许多算法的时间复杂度为O(n · log n )，例如：快速排序法的一般情形、快速傅里叶变换

参考资料

最新修订时间：2024-05-21 11:14

条目作者

概述

参考资料