n或nlog(n)比常数时间或对数时间好吗? [英] Is n or nlog(n) better than constant or logarithmic time?

问题描述

在Coursera上的Princeton教程中，讲师解释了遇到的常见的按增长顺序排列的函数.他说线性和线性运算运行时间是我们追求的目标"，他的理由是，随着输入大小的增加，运行时间也随之增加.我认为这是他犯错的地方，因为我以前曾听过他说线性增长顺序不能满足有效算法的要求.

In the Princeton tutorial on Coursera the lecturer explains the common order-of-growth functions that are encountered. He says that linear and linearithmic running times are "what we strive" for and his reasoning was that as the input size increases so too does the running time. I think this is where he made a mistake because I have previously heard him refer to a linear order-of-growth as unsatisfactory for an efficient algorithm.

在他讲话的同时，他还显示了一个图表，该图表绘制了不同的运行时间-恒定运行时间和对数运行时间看起来更加有效.那么，这是一个错误还是真的?

While he was speaking he also showed a chart that plotted the different running times - constant and logarithmic running times looked to be more efficient. So was this a mistake or is this true?

推荐答案

您缺少必须在其中进行这些声明的更广泛的上下文.不同类型的问题有不同的要求，甚至对解决这些问题的绝对必要"的工作甚至往往有理论上的下限，无论采用何种手段.

You're missing the broader context in which those statements must have been made. Different kinds of problems have different demands, and often even have theoretical lower bounds on how much work is absolutely necessary to solve them, no matter the means.

对于诸如对一个简单集合的每个元素进行排序或扫描之类的操作，您可以为这些操作对集合中的元素数量进行硬性下限，因为输出取决于输入的每个元素.[1]因此，O(n)或O(n * log(n))是最好的选择.

For operations like sorting or scanning every element of a simple collection, you can make a hard lower bound of the number of elements in the collection for those operations, because the output depends on every element of the input. [1] Thus, O(n) or O(n*log(n)) are the best one can do.

对于其他类型的操作，例如访问哈希表或链表的单个元素，或在排序集中进行搜索，该算法无需检查所有输入.在这些设置下，O(n)操作将非常缓慢.

For other kinds of operations, like accessing a single element of a hash table or linked list, or searching in a sorted set, the algorithm needn't examine all of the input. In those settings, an O(n) operation would be dreadfully slow.

[1]其他人会注意到，根据信息理论的论点，通过比较排序也具有n * log(n)下界.对于某些类型的输入，有一些基于非比较的排序算法可以胜过这种情况.

[1] Others will note that sorting by comparisons also has an n*log(n) lower bound, from information-theoretic arguments. There are non-comparison based sorting algorithms that can beat this, for some types of input.

这篇关于n或nlog(n)比常数时间或对数时间好吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！