银河式算法

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