logo标签列表

大O分析的算法

algorithmcomplexity-theorytime-complexityspace-efficiency
7

在结果的O符号和分析方式上，你们认为哪些算法的复杂度分析非常惊人（复杂、奇怪）？

6个回答
16

我有（相当）多的例子：

  • 并查集数据结构，支持（摊销）反阿克曼时间的操作。它特别好，因为数据结构非常容易编码。
  • Splay树，自平衡二叉树（也就是说，除了BST之外没有额外的信息 - 没有红 /黑信息。 摊销分析 实际上是为了证明splay树的边界而发明的; splay树在摊销对数时间内运行，但在最坏情况下线性时间。证明很酷。
  • Fibonacci堆，它以摊销常数时间执行大多数优先级队列操作，从而提高了Dijkstra算法和其他问题的运行时间。与splay树一样，有巧妙的“潜在函数”证明。
  • Bernard Chazelle算法以线性时间反阿克曼时间计算最小生成树。该算法使用soft堆，传统优先级队列的变体，但可能会出现一些“损坏”，查询可能无法正确回答。
  • 说到MST：Pettie和Ramachandran已经给出了最优算法，但我们不知道运行时间！
  • 许多随机算法都有有趣的分析。我只提一个例子：Delanay三角剖分可以通过逐点添加在期望的O（n log n）时间内计算出来；分析显然是复杂的，虽然我没有看到过。
  • 使用“位技巧”的算法可能很好，例如在O（n log log n）时间（和线性空间）中排序 - 没错，它通过使用比仅比较更多的内容打破了O（n log n）障碍。
  • Cache-oblivious算法通常具有有趣的分析。例如，cache-oblivious优先级队列（参见第3页）使用大小为n、n2/3、n4/9等的log log n个级别。
  • 数组上（静态）范围最小查询很棒。 标准证明会测试您与缩减的关系：范围最小查询被缩减为树中最小公共祖先，反过来又被缩减为特定类型的数组中的范围最小查询。最后一步也使用了一个可爱的技巧。
2
@p 这个答案可能还不错，尽管它只是一个链接。"Ackermann函数"足以在互联网上找到它，而这个问题——可能是不适合的——只是在征求算法，而不是解释。 - royhowie
2
这个比较简单，但梳排序还是让我觉得很神奇。
链接：http://en.wikipedia.org/wiki/Comb_sort 它是如此简单，以至于其大部分内容看起来像一个过于复杂的冒泡排序，但其时间复杂度为O（n * log [n]）。我觉得这有点令人印象深刻。
快速傅里叶变换算法的种类繁多也很令人印象深刻，证明它们正确性的数学处理十分迷幻，尝试自己证明其中一些算法很有趣。
链接：http://en.wikipedia.org/wiki/Fast_Fourier_transform 我可以相当容易地理解素数基、多重素数基和混合基算法，但对于适用于大小为素数的集合的算法，我觉得非常酷。
2

2D有序搜索分析非常有趣。你有一个数字数组NxN，其中每行从左到右排序，每列从上到下排序。任务是在数组中找到特定的数字。

递归算法：选择中间元素，与目标数字进行比较，丢弃四分之一的数组（取决于比较结果），对剩余的三个四分之一应用递归，这种算法非常有趣。

1

在编程方面，我倾向于选择非确定多项式复杂度，特别是考虑到它可能与多项式相同（尽管可能性很小）。同样，在理论上可以从量子计算中受益的任何事情都会得到我的认同（注意：这个集合并不是所有算法）。

另一个得到我的认同的是针对任意精度数的常见数学运算 - 在这里你必须考虑乘以大数比乘以小数更加费时。 Knuth对此进行了相当多的分析（这对任何人来说都不是新闻）。Karatsuba方法十分巧妙：通过数位将两个因数切成一半(A1;A2)(B1;B2)，然后分别计算A1 B1、A1 B2、A2 B1、A2 B2，最后将结果组合起来。如有需要，可进行递归处理...

Karatsuba算法确实很巧妙。然而，由于快速傅里叶变换执行卷积，因此可以用它来执行已知的最快乘法，前提是数字足够大以证明编写混合输入大小FFT并对其进行调整的麻烦是值得的。 - James Matta
嗯，我得查一下。组件需要多精确才能保证准确的整数乘法？ - Edmund
据我理解，您只需要足够的精度来保存最终数字。虽然FFT乘法技术也可以直接用于整数类型，总是给出准确的答案。我这里没有我的Knuth副本，但我认为他提到了这种技术并对其进行了讲解。 - James Matta
0

希尔排序。有许多不同增量的变体，其中大多数除了使复杂度分析更简单之外没有任何好处。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接