有没有一种被广泛使用的算法,该算法的时间复杂度更差比其它已知的算法,但它是一个更好的选择,所有的实际情况(更糟糕的复杂性,但更好的,否则)？
可接受的答案可能是以下形式:
有算法
A和B具有O(N**2)和O(N)时间复杂性相应,但B具有这样的大常数,它没有优于A为小于一个数量在宇宙原子的输入.
答案中的示例突出显示:
单纯形算法 - 最坏情况是指数时间 - 与凸优化问题的已知多项式时间算法相比.
中位数算法的中位数 - 最坏情况O(N**2)与已知O(N)算法.
回溯正则表达式引擎 - 最坏情况指数与基于O(N)Thompson NFA的引擎.
所有这些示例都利用了最坏情况和平均情况.
有关:
"更糟糕的是更好"的崛起.(出于这个问题的目的,"更糟的是更好"这个短语用于比文章更窄的(即 - 算法时间复杂度)意义上)
ABC集团力求完美.例如,他们使用基于树的数据结构算法,这些算法被证明是渐近大型集合的最佳选择(但对于小型集合来说并不是那么好).
如果没有能够存储这些大型集合的计算机(换句话说,大型集合在这种情况下不够大),这个例子就是答案.
用于方阵乘法的Coppersmith-Winograd算法是一个很好的例子(它是最快的(2008),但它不如更差的算法).还有其他人？ 来自维基百科的文章:"它并没有在实践中使用,因为它只为矩阵提供了一个优势,使它们无法被现代硬件处理(Robinson 2005)."
我目前有一个很长的列表,正在使用lambda函数f进行排序.然后我从前五个元素中选择一个随机元素.就像是:
f = lambda x: some_function_of(x, local_variable)
my_list.sort(key=f)
foo = choice(my_list[:4])
根据剖析器,这是我程序中的瓶颈.我怎样才能加快速度？是否有一种快速,内置的方式来检索我想要的元素(理论上不需要对整个列表进行排序).谢谢.
我知道如何获得单一最大值:
m = max([1,2])
2
我如何获得最大n元素？例如:
m = max([1,2,3,4,5], n=2)
[4,5]