logo标签列表

O(n log n)有一个简称吗？

algorithmcomplexity-theorybig-o
25

在算法分析中，我们通常用单个词来表示大多数复杂性：

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

我们经常遇到具有 O(n log n) 复杂度的算法（想想所有被排序复杂度支配的算法），但据我所知，在英语中没有单个词可以用来指代这种复杂度。这是我的知识盲区，还是我们关于计算复杂度的英语讨论中真正存在的空白？

4
对于所有注意音节数量的回答者，这不是关于优化（我在上面使用“速记”一词误导了你们），而更多地涉及到说流利的英语（即流畅；与这个插入语分开很不相似）。 - jemfinch
2
也许使用常见术语“nlogn”，它几乎没有其他含义，是流利、通用的英语。 - Joe Koberg
1
@Joe: 或许不是常用的英语，但是任何讨论算法复杂度的人都应该能够流利地使用它。 - David Thornley
6个回答
28

看起来是由Robert Sedgewick在书籍Algorithms In C中提出的。也叫做"准线性"或者"log线性"。然而，线性对数具有额外的优点，它不是一个重载的术语（"准线性"在经济学和微分方程中使用，而"log线性"在经济学和回归分析中使用）。

5
从其他答案的外观来看，我认为这不是常用语（我从未听说过），因此为了清晰起见，建议使用“inlogin”，否则您可能会被人奇怪的眼神盯着。尽管如此，请给它点赞 - 也许在未来，这将成为一个常用术语（奇怪的是它现在还不是）。 - Ian Henry
1
我怀疑该条目中的“原始材料”。... “约1,080个线性对数结果”google.com/search?q=linearithmic - Joe Koberg
4
"Linearithmic"这个词是由Robert Sedgewick在他的书《算法C语言实现》（Addison-Wesley 1990, ISBN 0-201-51425-7）中创造出来的，它将“linear”和“logarithmic”两个单词混合在一起。 - John Calsbeek
3
"Linearithmic" 在谷歌图书搜索结果中出现了32次，并且相比于 "quasilinear" 和 "loglinear"，它有一个额外的优点，即不用于其他数学目的。如果人们听说过它，那么这个问题可能就不存在了。 - John Calsbeek
1
@Roger，不是-1，因为将一个“非常”狭窄使用的术语推广为正确答案。那不是对Calsbeek评论的回复。 - P Shved
显示剩余4条评论
16
"

“en log en”的音节比“指数”或“对数”少。我认为大多数人都这么说。

"
7
为什么“double-you double-you double-you”（9个音节）可以简写成“world wide web”（3个音节）？ - Joe Koberg
这是真的，但是线性比n长，人们都这么说。 - Matthew Flaschen
4
@Joe — 或许这就是为什么很多人只说“dub-dub-dub”。当然，我不这样认为，我觉得那让你听起来像个说不清道不明的白痴。 - tvanfosson
是的，我记得上世纪90年代晚期电视技术访谈节目报道“万维网”，试图使用“双重 u 号”（dub-dub-dub）来表达它...... 真是糟糕。 - Joe Koberg
2
www？那可一点也不是Web 2.0！ - anon
“dub dub dub”? 真的吗？...Rub-a-dub-dub-dub？George DubDubDubya Bush？如果你这样做，会引发什么混乱呢？为了世界上所有美好的事物，请不要陷入这个陷阱！ - Platinum Azure
13
根据维基百科的说法，你可以称其为线性对数、对数线性或准线性。
这三个中，只有对数线性模型的意思比较清晰。虽然其他两个听起来确实很酷。 - Daniel DiPaolo
大约有1,080个关于"线性对数"的结果。http://www.google.com/search?q=linearithmic - Joe Koberg
1
我个人更喜欢“loglinear”。在实际应用中，也有变体 logilinear存在，但是这并没有被任何词典正式认可，似乎只在对数线性建模的背景下使用。 - Iain Samuel McLean Elder
维基百科已经说了。我将开始使用线性对数。 - rmeador
3

O(2^n)等于“O可怕”。

1

我不相信有这样的术语。

更相关的是这个想法：为什么你把指数（11个字符）称为O(2^n)（6个字符）的“速记”？

就我个人而言，我很高兴说“这个算法在en log en时间内运行”。这已经足够大多数人听到了。

1
现在，说“这个算法运行时间是2的n次方”与“这个算法运行时间是指数级”的区别。我认为后者更符合惯用语，并且更容易表达。 - David Thornley
1
是的，我同意你的观点。我从未声称指数函数不容易发音。但我认为没有一种简单、惯用的方式来表达线性增长函数和对数增长函数的乘积。 - Platinum Azure
-1

在中文中，没有单个词与O(nlogn)等效。你只需要花费额外的时间说出整个术语（注意：与“指数”有相同数量的音节）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接