查看“︁银河式算法”︁的源代码

{{Expert needed|subject=数学|time=2020-07-30T04:34:41+00:00}}
'''银河式算法'''（{{lang|en|Galactic Algorithm}}）不是某一种具体[[算法]]的名称，而是一类对于极大规模数据表现特别优异的复杂算法。这类算法在常规问题中往往无法展现出优势，甚至效率低于一般的解决方案，而当数据规模足够大时，效率将提升到不可思议的程度。这里的“足够大”实际上已经脱离了现实需求，以至于这类算法从未在实践中发挥作用。“银河式算法”一词首先由[[理查德·立普顿]]和[[肯·里根]]提出<ref>{{cite book |author=Lipton, Richard J., and Kenneth W. Regan |chapter=David Johnson: galactic algorithms |title=People, Problems, and Proofs |publisher=Springer Berlin |location=Heidelberg |year=2013 |pages=109–112 |chapter-url=https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ |access-date=2020-07-29 |archive-date=2020-08-02 |archive-url=https://web.archive.org/web/20200802140355/https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ |dead-url=no }}</ref>，“银河式”意味着面对数据规模之大如银河中的繁星，且“不会与地球上的问题打交道”。

银河式算法的著名示例包括一种大整数[[乘法]]<ref>{{cite article |url=https://hal.archives-ouvertes.fr/hal-02070778 |title=Integer multiplication in time O(''n''&nbsp;log&nbsp;''n'') |author=David Harvey and Joris Van Der Hoeven |date=March 2019 |access-date=2020-07-29 |archive-date=2019-04-08 |archive-url=https://web.archive.org/web/20190408180939/https://hal.archives-ouvertes.fr/hal-02070778 |dead-url=no }}</ref>，其基于 <math>1729</math> 维的[[快速傅里叶变换]]<ref>{{cite web |url=https://phys.org/news/2019-04-weve-quicker-big.html |title=We've found a quicker way to multiply really big 数值s |author=David Harvey |date=2019-04-10 |publisher=Phys.org |accessdate=2020-07-29 |archive-date=2020-06-30 |archive-url=https://web.archive.org/web/20200630110731/https://phys.org/news/2019-04-weve-quicker-big.html |dead-url=no }}</ref><ref>{{Cite journal|last=David|first=Harvey|last2=Hoeven|first2=Joris van der|date=2019-03-18|title=Integer multiplication in time O(n log n)|url=https://hal.archives-ouvertes.fr/hal-02070778/document|journal=HAL|volume=hal-02070778|pages=|via=|access-date=2020-07-29|archive-date=2020-07-22|archive-url=https://web.archive.org/web/20200722182853/https://hal.archives-ouvertes.fr/hal-02070778/document|dead-url=no}}</ref>。这意味着只有当数值至少达到 <math>2^{1729^{12}}</math> （即 <math>10^{10^{38}}</math>）位[[十进制]]数字之后,这种算法的优势才能发挥出来，而这个数量级已经远远超过[[宇宙]]中原子的数量，因此这种算法从未被真正使用过<ref>{{cite web |url=http://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-数值s-114923 |title=We've found a quicker way to multiply really big numbers. Quote, from one of the authors of the algorithm: "The new algorithm is not really practical in its current form, because the proof given in our paper only works for ludicrously large 数值s. Even if each digit was written on a hydrogen atom, there would not be nearly enough room available in the observable universe to write them down."}}</ref>。

即便银河式算法看起来没有用处，但有关这类算法的思想和讨论仍然对[[计算机科学]]大有裨益。
* 一种看似不切实际的算法所展现出来的新技术，可能会最终转变为比当下更好的实用算法。
* 计算机的高速发展可能会使解决一些原本不曾邂逅的大规模问题变得迫在眉睫，算力和存储空间的提升可能会为一些原本难以实施的复杂算法提供实践机会。
* 不切实际的算法会证明或证伪当下一些猜想的边界。据立普顿所说，“这一点非常重要，并且通常是我们找到此类算法的重要原因。例如，如果明天发现一个[[因式分解]]算法具有巨大但可证明的多项式时间复杂度，即使我们深信该算法可能永远不会使用，但仍会影响我们未来对于因式分解相关技术的研究，为更新颖、更可靠的想法提供经验。”同样，一种用于解决[[布尔可满足性问题]]的、[[时间复杂度]]为 <math>O\left(n^{2^{100}}\right)</math> 的算法虽然在实践中不可用，但仍然有益于人们探索[[P=NP问题]]——这一计算机科学中最重要的开放性问题，也是[[千禧年大獎難題|千禧年大奖问题]]之一<ref>{{cite journal |author=Fortnow, L. |year=2009 |title=The status of the P versus NP problem |journal=Communications of the ACM |volume=52 |issue=9 |pages=78–86 |url=http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf |doi=10.1145/1562164.1562186 |access-date=2020-07-29 |archive-date=2020-05-26 |archive-url=https://web.archive.org/web/20200526035035/http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf |dead-url=no }}</ref>。

== 范例 ==

有几种众所周知的算法具有无与伦比的渐近行为，但仅针对难以想象的极大规模问题：
* [[矩阵乘法]]：第一次将 <math>O(N^3)</math> 的暴力算法改进到 <math>O(N^{2.807})</math> 的是[[史恩哈格-施特拉森算法|施特拉森算法]]，这是一种递归算法。它的确曾在实践中被使用过，严格来说并不属于银河式算法。[[库珀史密斯-温诺格勒算法]]在其基础上利用复杂的群论进一步改进，使时间复杂度降低到 <math>O(N^{2.373})</math>。而这是“银河式”的——“尽管如此，我们强调这样的改进仅在理论上有意义，因为快速矩阵乘法的复杂性所涉及的巨大常数使这些算法不切实际。”<ref>{{citation
 | last = Le Gall | first = F.
 | arxiv = 1204.1111
 | contribution = Faster algorithms for rectangular matrix multiplication
 | doi = 10.1109/FOCS.2012.80
 | pages = 514–523
 | title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
 | year = 2012}}.</ref>
* [[克劳德·香农]]提出了一种简单但只在理论中可行的程序。它需要对每一个可能的、长度为 N [[位元|比特]]的信息标记一个随机编码，接着通过寻找最近的编码进行译读。如果 N 被取得足够大，它将会胜过任意现存编码，并任意接近信道容量。不幸的是，任何能够大于现存编码的 N 是不现实的<ref>{{cite web |url=https://news.mit.edu/2010/explained-shannon-0115 |title=Explained: The Shannon limit |publisher=MIT News Office |author=Larry Hardesty |date=2010-01-19 |accessdate=2020-07-29 |archive-date=2020-08-28 |archive-url=https://web.archive.org/web/20200828184218/https://news.mit.edu/2010/explained-shannon-0115 |dead-url=no }}</ref>。尽管这些编码从未被使用，却激发了数十年来队更实用的算法的研究。这些算法如今可以达到任意接近信道容量的速率<ref>{{cite web |url=https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-451-principles-of-digital-communication-ii-spring-2005/video-lectures/chap13.pdf |title=Capacity-Approaching Codes |accessdate=2020-07-29 |archive-date=2019-12-07 |archive-url=https://web.archive.org/web/20191207155344/https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-451-principles-of-digital-communication-ii-spring-2005/video-lectures/chap13.pdf |dead-url=no }}</ref>。
* 在[[图论]]中，[[决定性问题|确定]]图 ''G'' 是否包含[[图子式]] ''H'' ，通常是一个[[NP-完全]]的问题。但当 ''H'' 固定时，该问题可以在[[多项式时间]]内得到解决。测试 ''H'' 是否为 ''G'' 的图子式，在这里有着 <math>O( n^2 )</math> 的复杂度<ref name="kkr12">{{cite journal |author=Kawarabayashi, K. I., Kobayashi, Y., & Reed, B. |year=2012 |title=The disjoint paths problem in quadratic time |journal=Journal of Combinatorial Theory, Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004}}</ref>，此处 ''n'' 是 ''G'' 所包含顶点的数量，且[[大O记号]]的常数是以'''超指数的（superexponential）'''增长趋势依赖 ''H''。这个常数大于 <math> c > 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h / 2) ) ) </math> （此处利用[[高德納箭號表示法]]），其中 ''h'' 是 <math>H</math> 的顶点数<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |doi=10.1016/0196-6774(87)90043-5 }}</ref>。
* 对于密码学家来说，“找钥匙开锁”比暴力攻击要快得多，即对序列中的每个可能的[[密钥]]尝试一次解密操作。即使这些方法往往广为人知，但对于当下技术水平而言仍然是行不通的。最好情况下，攻破 <math>128</math> 位 [[高级加密标准|AES 算法]]仅需 <math>2^{126}</math> 次攻击<ref name=":0">{{cite book |author=Biaoshuai Tao |title = Information Security and Privacy|volume = 9144|pages = 39–56|author2=Hongjun Wu |last-author-amp=yes |date=2015|doi=10.1007/978-3-319-19962-7_3 |series = Lecture Notes in Computer Science|isbn = 978-3-319-19961-0}}</ref>。尽管尚无法实际实践，但理论上的突破有时可以提供对漏洞模式的深入了解。
* 用于分解大数的新算法不断出现，但如果它们“出现”，则意味着它们尚未达到足够的效率，因此试验仍在继续。一个例子是“[https://www.1universe.gpe.pl/prime/sources.html Primorial Riddle] {{Wayback|url=https://www.1universe.gpe.pl/prime/sources.html |date=20240627105837 }}”，根据未经证实的报道，它已经非常有效。
* 存在一种被称为“Hutter 搜索”的单一算法，可以在渐近最佳时间内解决任何定义明确的问题。但需要注意的是，这种算法运行起来的隐藏时间复杂度常数是如此之大，以至于难以发挥什么有效作用<ref>{{cite arxiv|last=Hutter|first=Marcus|date=2002-06-14|title=The Fastest and Shortest Algorithm for All Well-Defined Problems|eprint=cs/0206022}}</ref><ref>{{Cite journal|last=Gagliolo|first=Matteo|date=2007-11-20|title=Universal search|journal=Scholarpedia|language=en|volume=2|issue=11|pages=2575|doi=10.4249/scholarpedia.2575|issn=1941-6016|bibcode=2007SchpJ...2.2575G}}</ref>。

== 参考文献 ==
{{Reflist}}

[[Category:數學表示法]]
[[Category:渐近分析]]
[[Category:算法分析]]