Big O 分析算法

发布于 2024-07-14 19:00:05 字数 55 浏览 9 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

俯瞰星空 2024-07-21 19:00:05

我有（相当）几个例子：

union-find 数据结构，它支持操作在（摊销）逆阿克曼时间中。它特别好，因为数据结构非常容易编码。
Splay 树，它们是自平衡二叉树（即，除了存储之外不存储任何额外信息） BST——没有红/黑信息摊销分析本质上是为了证明展开树的界限而发明的。 ; 展开树以对数时间运行，但最坏情况的线性时间很酷
。 noreferrer">斐波那契堆，它在摊销常数时间内执行大部分优先级队列操作，从而提高了Dijkstra 算法和其他问题一样，伯纳德·查泽勒 (Bernard Chazelle) 的算法也有巧妙的“势函数”证明，
用于计算线性时间逆阿克曼时间的最小生成树。 ="http://en.wikipedia.org/wiki/Soft_heap" rel="noreferrer">软堆，传统优先级队列，但可能会发生一些“损坏”并且查询可能无法正确回答。
关于 MST 主题：Pettie 和给出了一种最佳算法Ramachandran，但我们不知道运行时间！
许多随机算法都有有趣的分析。我只提一个例子：Delaunay 三角剖分可以在预期的 O(n log n) 时间内通过计算出来逐步添加点；分析显然很复杂，尽管我还没有看到。
使用“位技巧”的算法可以很简洁，例如以 O(n log log n) 时间（和线性空间）——没错，它通过使用不仅仅是比较来打破 O(n log n) 障碍。
缓存遗忘算法通常有有趣的分析。例如，缓存忽略优先级队列（请参阅第 3 页）使用 log log n 级别，大小为 n、n^2/3、n^4/9 等。
数组上的（静态）最小范围查询很简洁。标准证明测试您在减少方面的极限：最小范围查询被简化为树中的最小公共祖先，而树又被简化为特定种类数组中的最小范围查询。最后一步也使用了一个可爱的技巧。

I have (quite) a few examples:

The union-find data structure, which supports operations in (amortized) inverse Ackermann time. It's particularly nice because the data structure is incredibly easy to code.
Splay trees, which are self-balancing binary trees (that is, no extra information is stored other than the BST -- no red/black information. Amortized analysis was essentially invented to prove bounds for splay trees; splay trees run in amortized logarithmic time, but worst-case linear time. The proofs are cool.
Fibonacci heaps, which perform most of the priority queue operations in amortized constant time, thus improving the runtime of Dijkstra's algorithm and other problems. As with splay trees, there are slick "potential function" proofs.
Bernard Chazelle's algorithm for computing minimum spanning trees in linear times inverse Ackermann time. The algorithm uses soft heaps, a variant of the traditional priority queue, except that some "corruption" might occur and queries might not be answered correctly.
While on the topic of MSTs: an optimal algorithm has been given by Pettie and Ramachandran, but we don't know the running time!
Lots of randomized algorithms have interested analyses. I'll only mention one example: Delaunay triangulation can be computed in expected O(n log n) time by incrementally adding points; the analysis is apparently intricate, though I haven't seen it.
Algorithms that use "bit tricks" can be neat, e.g. sorting in O(n log log n) time (and linear space) -- that's right, it breaks the O(n log n) barrier by using more than just comparisons.
Cache-oblivious algorithms often have interesting analyses. For example, cache-oblivious priority queues (see page 3) use log log n levels of sizes n, n^2/3, n^4/9, and so on.
(Static) range-minimum queries on arrays are neat. The standard proof tests your limits with respect to reduction: range-minimum queries is reduced to least common ancestor in trees, which is in turn reduced to a range-minimum queries in a specific kind of arrays. The final step uses a cute trick, too.

回复收藏 0 原文

才能让你更想念 2024-07-21 19:00:05

阿克曼函数。

回复收藏 0 原文

夜空下最亮的亮点 2024-07-21 19:00:05

这个有点简单，但梳排序让我有点震惊。

http://en.wikipedia.org/wiki/Comb_sort

这是一个非常简单的算法它的大部分内容读起来就像一个过于复杂的冒泡排序，但它的复杂度是 O(n*Log[n])。我觉得这有点令人印象深刻。

大量的快速傅立叶变换算法也令人印象深刻，证明其有效性的数学是令人迷惑的，尝试自己证明一些算法很有趣。

http://en.wikipedia.org/wiki/Fast_Fourier_transform

我可以很容易地理解素数基数、多个素数基数和混合基数算法，但适用于大小为素数的集合的算法非常酷。

回复收藏 0 原文

柒夜笙歌凉 2024-07-21 19:00:05

2D有序搜索分析相当有趣。您有一个由 NxN 组成的二维数值数组，其中每行从左到右排序，每列从上到下排序。任务是在数组中找到特定的数字。

递归算法：选取中间的元素，与目标数进行比较，丢弃数组的四分之一（取决于比较的结果），递归地应用到剩余的 3 个四分之一，分析起来很有趣。

回复收藏 0 原文

双手揣兜 2024-07-21 19:00:05

非确定性多项式复杂性得到了我的投票，特别是考虑到它可能与多项式相同的可能性（诚然被认为不太可能）。同样，任何理论上可以从量子计算中受益的东西（注意这组绝不是所有算法）。

我投票的另一个问题是对任意精度数字的常见数学运算——在这里你必须考虑诸如乘以大数比乘以小数更昂贵的事情。 Knuth 对此有相当多的分析（这对任何人来说都不是什么新闻）。唐叶的方法非常简洁：将两个因数按数字减半(A1;A2)(B1;B2)，然后分别乘以A1 B1、A1 B2、A2 B1、A2 B2，然后将结果组合起来。如果需要的话可以递归...

回复收藏 0 原文