是否有O(n log n)的简写术语？

Question

对于我们在算法分析中遇到的大多数复杂性,我们通常只有一个单词:

• O(1) =="常数"
• O(log n) =="对数"
• O(n) =="线性"
• O(n^2) =="二次"
• O(n^3) =="立方"
• O(2^n) =="指数"

我们遇到O(n log n)具有一定规律性的复杂算法(想想所有算法都以排序复杂性为主)但据我所知,我们在英语中没有一个单词能用来指代那种复杂性.这是我的知识差距,还是我们关于计算复杂性的英语话语中的真正差距？

Answer 1

• O(n log n)== "linearithmic"

似乎是由Robert Sedgewick在" 算法在C "一书中创造的.也称为拟线性或对数线性.然而,线性方法还有一个额外的好处,即不是一个过载的术语(拟线性用于经济学和微分方程,而对数线性用于经济学和回归分析).

Answer 2

"en log en"具有比"指数"或"对数"更少的音节.我想大多数人都这么说.

Answer 3

根据维基百科,你可以把它叫做linearithmic,对数线性或拟线性.