相关疑难解决方法(0)

有没有一种被广泛使用的算法,该算法的时间复杂度更差比其它已知的算法,但它是一个更好的选择,所有的实际情况(更糟糕的复杂性,但更好的,否则)？

可接受的答案可能是以下形式:

有算法A和B具有O(N**2)和O(N)时间复杂性相应,但B 具有这样的大常数,它没有优于A为小于一个数量在宇宙原子的输入.

答案中的示例突出显示:

• 单纯形算法 - 最坏情况是指数时间 - 与凸优化问题的已知多项式时间算法相比.

• 中位数算法的中位数 - 最坏情况O(N**2)与已知O(N)算法.

• 回溯正则表达式引擎 - 最坏情况指数与基于O(N)Thompson NFA的引擎.

所有这些示例都利用了最坏情况和平均情况.

是否存在不依赖于最坏情况与平均情况之间差异的示例？

有关:

• "更糟糕的是更好"的崛起.(出于这个问题的目的,"更糟的是更好"这个短语用于比文章更窄的(即 - 算法时间复杂度)意义上)

• Python的设计理念:

  ABC集团力求完美.例如,他们使用基于树的数据结构算法,这些算法被证明是渐近大型集合的最佳选择(但对于小型集合来说并不是那么好).

  如果没有能够存储这些大型集合的计算机(换句话说,大型集合在这种情况下不够大),这个例子就是答案.

• 用于方阵乘法的Coppersmith-Winograd算法是一个很好的例子(它是最快的(2008),但它不如更差的算法).还有其他人？ 来自维基百科的文章:"它并没有在实践中使用,因为它只为矩阵提供了一个优势,使它们无法被现代硬件处理(Robinson 2005)."

我有一个很长的字符串，几乎有一兆字节长，我需要将其写入文本文件。常规的

file = open("file.txt","w")
file.write(string)
file.close()

可以，但是太慢了，有什么办法可以写得更快吗？

我正在尝试将几百万位数字写入文本文件，该数字约为math.factorial(67867957)

这是分析中显示的内容：

    203 function calls (198 primitive calls) in 0.001 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 re.py:217(compile)
        1    0.000    0.000    0.000    0.000 re.py:273(_compile)
        1    0.000    0.000    0.000    0.000 sre_compile.py:172(_compile_charset)
        1    0.000    0.000    0.000    0.000 sre_compile.py:201(_optimize_charset)
        4    0.000    0.000    0.000    0.000 sre_compile.py:25(_identityfunction)
      3/1    0.000    0.000    0.000    0.000 sre_compile.py:33(_compile)
        1    0.000    0.000    0.000    0.000 sre_compile.py:341(_compile_info)
        2    0.000    0.000 …

19世纪1月,建立了一项新的世界纪录:迄今为止发现的最大素数之一.这个数字达到了2 ^ 74207281 - 1,拥有超过2230万位数字.我在youtube上的numberphile频道上看到,他们将这个数字打印在一本由3部分组成的书中.现在我的问题是:你如何获得一个如此大的数字的字符串表示？显然这需要相当长的时间,但最有效的方法是什么？

我在Java中知道这样做的唯一方法是使用BigIntegers,这是最好的方法吗？用其他语言怎么样？