你们发现所有算法在这两个方面都有惊人的（艰难的，奇怪的）复杂性分析 - 产生的 O 表示法和分析方式的唯一性？
VarunGupta
问问题
1906 次
6 回答
16
我有（相当）几个例子：
- union-find数据结构，它支持（摊销）逆阿克曼时间的操作。它特别好，因为数据结构非常容易编码。
- 展开树，它们是自平衡二叉树（也就是说，除了 BST 之外没有存储额外的信息——没有红/黑信息。 摊销分析本质上是为了证明展开树的界限而发明的；展开树以摊销的对数时间运行, 但最坏情况下的线性时间。证明很酷。
- 斐波那契堆，它在摊销的常数时间内执行大部分优先级队列操作，从而改善了Dijkstra 算法的运行时间和其他问题。与展开树一样，也有巧妙的“潜在功能”证明。
- Bernard Chazelle 的算法，用于以线性时间逆阿克曼时间计算最小生成树。该算法使用软堆，这是传统优先级队列的一种变体，但可能会发生一些“损坏”并且可能无法正确回答查询。
- 虽然关于 MST 的主题：Petti和 Ramachandran 给出了一个最优算法，但我们不知道运行时间！
- 许多随机算法都有感兴趣的分析。我只提一个例子：Delaunay 三角剖分可以在预期的 O(n log n) 时间内通过递增地添加点来计算；分析显然是错综复杂的，虽然我还没有看到它。
- 使用“位技巧”的算法可以很简洁，例如在 O(n log log n) 时间（和线性空间）中排序——没错，它通过使用不仅仅是比较来打破 O(n log n) 障碍。
- 缓存遗忘算法通常有有趣的分析。例如，缓存忽略优先级队列（参见第 3 页）使用大小为 n、n 2/3、n 4/9等的 log log n 级别。
- 数组上的（静态）范围最小查询很整洁。标准证明测试您在减少方面的限制：范围最小查询被减少到树中的最不共同祖先，这反过来又被减少到特定类型数组中的最小范围查询。最后一步也使用了一个可爱的技巧。
于 2009-02-23T08:14:46.020 回答
2
于 2009-02-23T07:43:32.867 回答
2
这个有点简单，但梳排序让我有点吃惊。
http://en.wikipedia.org/wiki/Comb_sort
它是一个非常简单的算法，读起来像一个过于复杂的冒泡排序，但它是 O(n*Log[n])。我觉得这有点令人印象深刻。
过多的快速傅立叶变换算法也令人印象深刻，证明它们有效性的数学是迷幻的，我自己尝试证明一些很有趣。
http://en.wikipedia.org/wiki/Fast_Fourier_transform
我可以相当容易地理解素数基数、多个素数基数和混合基数算法，但是在大小为素数的集合上工作的算法非常酷。
于 2009-02-23T07:50:28.903 回答
2
二维有序搜索分析非常有趣。你有一个二维数字数组 NxN ，其中每一行从左到右排序，每一列从上到下排序。任务是在数组中找到一个特定的数字。
递归算法：选择中间的元素，与目标数比较，丢弃数组的四分之一（取决于比较的结果），递归应用到剩余的 3 个四分之一，分析起来很有趣。
于 2009-02-24T08:46:51.693 回答
1
非确定性多项式复杂性得到了我的投票，尤其是在（被认为不太可能）它可能与多项式相同的可能性的情况下。同样，理论上任何可以从量子计算中受益的东西（注意这组绝不是所有算法）。
我投票的另一个是对任意精度数字的常见数学运算——这是你必须考虑的事情，比如乘以大数字比乘以小数字更昂贵。Knuth 对此有很多分析（这对任何人来说都不应该是新闻）。Karatsuba 的方法非常巧妙：将两个因子除以 (A1;A2)(B1;B2) 的位数，然后分别乘以 A1 B1、A1 B2、A2 B1、A2 B2，然后合并结果。如果需要，递归...
于 2009-02-23T07:48:27.660 回答
0
贝壳排序。有大量不同增量的变体，其中大多数除了使复杂性分析更简单之外没有任何好处。
于 2009-07-30T14:26:26.507 回答