银河式算法 银河式算法Galactic Algorithm不是某一种具体算法的名称而是一类对于极大规模数据表现特别优异的复杂算法这类算法在常规问题中往往无法展现出优势甚至效率低于一般的解决方案而当数据规模足够大时效率将提升到不可思议的程度这里的足够大实际上已经脱离了现实需求以至于这类算法从未在实践中发挥作用银河式算法一词首先由理查德立普顿和肯里根提出银河式意味着面对数据规模之大如银河中的繁星且不会与地球上的问题打交道 银河式算法的著名示例包括一种大整数乘法其基于  displaystyle  维的快速傅里叶变换这意味着只有当数值至少达到    displaystyle  即    displaystyle  位十进制数字之后这种算法的优势才能发挥出来而这个数量级已经远远超过宇宙中原子的数量因此这种算法从未被真正使用过 即便银河式算法看起来没有用处但有关这类算法的思想和讨论仍然对计算机科学大有裨益 一种看似不切实际的算法所展现出来的新技术可能会最终转变为比当下更好的实用算法 计算机的高速发展可能会使解决一些原本不曾邂逅的大规模问题变得迫在眉睫算力和存储空间的提升可能会为一些原本难以实施的复杂算法提供实践机会 不切实际的算法会证明或证伪当下一些猜想的边界据立普顿所说这一点非常重要并且通常是我们找到此类算法的重要原因例如如果明天发现一个因式分解算法具有巨大但可证明的多项式时间复杂度即使我们深信该算法可能永远不会使用但仍会影响我们未来对于因式分解相关技术的研究为更新颖更可靠的想法提供经验同样一种用于解决布尔可满足性问题的时间复杂度为 O  n    displaystyle Oleftnright 的算法虽然在实践中不可用但仍然有益于人们探索PNP问题这一计算机科学中最重要的开放性问题也是千禧年大奖问题之一