大O分析的算法

人们发现所有算法都具有惊人的(艰难的,奇怪的)复杂性分析 - 结果O符号和分析方式的唯一性？

我有(很)一些例子:

的合并-查找数据结构,它支持在(摊销)逆阿克曼时间的操作.它特别好,因为数据结构非常容易编码.

Splay树,它们是自平衡的二叉树(也就是说,除了BST之外没有存储额外的信息 - 没有红/黑信息. 摊销分析基本上被发明用于证明展开树的界限;展开的树以摊销的对数时间运行,但最坏情况线性时间.证明很酷.

Fibonacci堆,以摊销的常数时间执行大多数优先级队列操作,从而改善Dijkstra算法的运行时间和其他问题.与splay树一样,有光滑的"潜在功能"证明.

Bernard Chazelle的算法用于计算线性时间逆阿克曼时间的最小生成树.该算法使用软堆,这是传统优先级队列的变体,除了可能发生某些"损坏"并且可能无法正确回答查询.

关于MST的主题:Pettie和Ramachandran给出了一个最优算法,但我们不知道运行时间!

许多随机算法都有兴趣分析.我只提一个例子:Delaunay三角剖分可以通过逐步增加点来计算预期的O(n log n)时间; 尽管我还没有看到它,但分析显然是错综复杂的.

使用"位技巧"的算法可以很整洁,例如在O(n log log n)时间(和线性空间)中排序 - 这是正确的,它通过使用不仅仅是比较来打破O(n log n)障碍.

缓存遗忘算法通常有趣的分析.例如,缓存无关的优先级队列(参见第3页)使用大小为n,n ^2/3,n ^4/9等的日志日志级别.

数组上的(静态)范围最小查询是整齐的.的标准证明测试相对于自己的极限还原:范围最小查询被减少到在树木至少共同的祖先,其又在特定减小到范围最小查询样阵列.最后一步也使用了一个可爱的技巧.