大 O 分析算法

Question

你们发现哪些算法在结果 O 表示法和分析方式的独特性方面具有惊人的(艰难的、奇怪的)复杂性分析？

Answer 1

我有(相当)几个例子:

• union-find数据结构，它支持(摊销的)逆阿克曼时间的操作。它特别好，因为数据结构非常容易编码。
• Splay trees ，它们是自平衡二叉树(也就是说，除了 BST 之外没有存储额外的信息——没有红色/黑色信息。Amortized analysis 本质上是为了证明 splay 树的边界而发明的；splay 树以 摊销的方式运行 对数时间，但最坏情况下的线性时间。证明很酷。
• Fibonacci heaps ，它在摊销常数时间内执行大部分优先级队列操作，从而提高了 Dijkstra's algorithm 的运行时间和其他问题。与 splay 树一样，有巧妙的“潜在功能”证明。
• Bernard Chazelle 的算法，用于计算线性时间反阿克曼时间的最小生成树。该算法使用 soft heaps ，传统的变体 priority queue ，除了可能会发生一些“损坏”并且可能无法正确回答查询。
• 关于 MST 的主题:最佳算法是 given by Pettie and Ramachandran , 但我们不知道运行时间!
• 许多随机算法都有有趣的分析。我只会提到一个例子:Delaunay 三角剖分可以在预期的 O(n log n) 时间内通过 incrementally adding points 计算得出。 ;分析显然很复杂，虽然我还没有看到。
• 使用“位技巧”的算法可以很简洁，例如sorting in O(n log log n)时间(和线性空间)——没错，它通过使用的不仅仅是比较来打破 O(n log n) 的障碍。
• Cache-oblivious algorithms经常有有趣的分析。例如，cache-oblivious priority queues (参见第 3 页)使用大小为 n、n^2/3、n^4/9 等的 log log n 级别。
• (静态)对数组的范围最小查询很简洁。 standard proof测试您在减少方面的限制:范围最小查询减少到树中的最小公共(public)祖先，这又减少到特定种类数组中的范围最小查询。最后一步也使用了一个可爱的技巧。