tem*_*boy 7 algorithm time-complexity
在Coursera的普林斯顿教程中,讲师解释了遇到的常见增长顺序函数.他说线性和线性运行时间是"我们努力的",他的推理是随着输入尺寸的增加,运行时间也增加.我认为这是他犯了一个错误的地方,因为我之前听过他提到线性增长顺序对于一个有效的算法是不能令人满意的.
在他讲话时,他还展示了绘制不同运行时间的图表 - 恒定和对数运行时间看起来效率更高.这是一个错误,还是这个？
Con*_*uit 24
在上下文中考虑O(n)和O(n log n)函数比O(1)和O(log n)函数具有更好的复杂性是错误的.在查看大O符号的典型复杂情况时:
O(1)<O(log n)<O(n)<O(n log n)<O(n ^ 2)
请注意,这并不一定意味着它们总是在性能方面更好 - 我们可能有一个O(1)函数需要很长时间才能执行,即使它的复杂性不受元素数量的影响.这样的函数在大O表示法中看起来比O(log n)函数看起来更好,但实际上可能实际上表现更差.
一般来说:当n足够高时,具有较低复杂度的函数(大O表示法)将胜过具有更大复杂度的函数(大O表示法).
Phi*_*ler 13
你错过了必须做出这些陈述的更广泛的背景.不同类型的问题有不同的要求,并且通常甚至在解决它们的绝对必要的工作量方面有理论上限,无论手段如何.
对于排序或扫描简单集合的每个元素等操作,您可以为这些操作设置集合中元素数量的硬下限,因为输出取决于输入的每个元素.[1]因此,O(n)或O(n*log(n))是最好的.
对于其他类型的操作,例如访问哈希表或链表的单个元素,或搜索有序集,该算法不需要检查所有输入.在这些设置中,O(n)操作将非常慢.
[1]其他人会注意到,通过比较排序也有一个n*log(n)下界,来自信息论的论点.对于某些类型的输入,有基于非比较的排序算法可以击败它.