是否有任何 O(1/n) 算法？

或者其他任何小于 O(1) 的东西？

我在每一轮递归中求解两个方程：

X = A - inv(B) * Y * inv(B)，X = X + A' * inv(B) * A，

我这样解决问题：

C = inv(B) Y <=> BC = Y，求解 C. D = C inv(B) <=> DB = C <=> B'D' = C'，求解 D'

E = inv(B)*A <=> BE = A，求解 E。

所有矩阵都会随着时间而变化，所以我必须在每次递归时再次执行此操作（或反转）。N 通常约为 1-10，可能更多，但通常是这样的。B 是正定的，所以我可以在因式分解中使用 cholesky，然后求解多个右手边的方程。

这比仅仅反转 B 然后用它进行矩阵乘法要慢得多还是快得多？一个反演与求解三个线性方程组（还有另一个方程）加上一些转置。我认为它至少在数值上比反转更稳定？

谢谢。

有哪些 Big-O 表示法 [1] 在实践中失败的例子？

也就是说：算法的 Big-O 运行时间什么时候会预测算法 A 比算法 B 快，而实际运行时算法 B 会更快？

稍微宽泛一点：关于算法性能的理论预测何时与观察到的运行时间不匹配？非大 O 预测可能基于搜索树中的平均/预期旋转次数，或排序算法中的比较次数，表示为因子乘以元素数量。

澄清：

尽管有些答案说了什么，但 Big-O 表示法旨在预测算法性能。也就是说，它是一个有缺陷的工具：它只谈论渐近性能，它模糊了常数因素。它这样做是有原因的：它旨在预测算法性能，而与您在哪台计算机上执行算法无关。

我想知道的是：这个工具的缺陷什么时候表现出来？我发现 Big-O 表示法相当有用，但远非完美。有哪些陷阱、边缘情况和陷阱？

我正在寻找的一个例子：使用斐波那契堆而不是二进制堆运行 Dijkstra 的最短路径算法，你得到 O(m + n log n) 时间与 O((m+n) log n)，对于 n顶点和 m 条边。您预计斐波那契堆迟早会提高速度，但在我的实验中从未实现过速度提高。

（没有证据的实验证据表明，在均匀随机边权重上运行的二进制堆花费 O(1) 时间而不是 O(log n) 时间；这是实验的一个大问题。另一个难以计数的问题是预期的调用 DecreaseKey 的次数）。

[1] 实际上，失败的不是符号，而是符号所代表的概念，以及预测算法性能的理论方法。</反迂腐>

关于接受的答案：

我已经接受了一个答案，以突出我希望得到的答案。存在许多同样好的答案:) 我喜欢这个答案的地方在于，它提出了一个通用规则，用于何时 Big-O 表示法“失败”（当缓存未命中主导执行时间时），这也可能增加理解（在某种意义上我不确定如何最好地表达 ATM）。

存在哪些算法运行时间模型？

我们都期望归并排序比冒泡排序更快，并注意归并排序使得 O(n log n) 与 O(n ² ) 的冒泡排序进行比较。

对于其他算法，您可以计算其他操作（比较和交换除外），例如指针取消引用、数组查找、固定大小整数的算术等。

还有哪些其他方法来模拟执行时间？

我自己知道的一个是计算从磁盘读取和写入磁盘的块数；请参阅我对 Big-O 表示法何时失败的回答？冗长的描述。

另一个是计算缓存未命中的数量。这通过查看内存层次结构的所有级别来扩展 I/O 模型。

第三，对于分布式算法（例如在安全多方计算中），是计算通过网络传输的数据量（通常以通信轮数或消息数来衡量）。

为了预测算法的性能，还有哪些其他有趣的事情可以计算（而不是计算！）？

另外，这些模型有多好？ 据我所知，缓存遗忘算法与磁盘数据的 I/O 效率算法相比具有竞争力，但对于内存算法则不然。

特别是：这些模型在哪些特定情况下错误地预测了相对性能？根据我自己的实验，当数据小到足以放入内存时，斐波那契堆不会加速 Dijstra 的最短路径（相对于二进制堆）。

是否有至少具有O(log n)插入、删除、访问和合并的地图数据结构？

大多数自平衡二叉树，例如AVL 树和红黑树，都具有这些属性中的大部分，但我相信它们具有O(n log n)合并功能。有没有合并速度更快的数据结构？

编辑：我环顾四周，找不到这样的东西。如果没有这样的数据结构，我很想了解为什么这是不可能的。

我碰巧在维基百科上读到，在不相交集（联合两个元素，找到特定元素的父元素）上每次操作的摊销时间是 O(a(n))，其中 a(n) 是逆阿克曼函数，它会增长非常快。

谁能解释为什么这是真的？

我在 Big Oh Notation 上度过了最艰难的时光。我想知道你能不能帮帮我。使用这两个函数的 big-Oh 表示法，增长率的最小上限是多少？

我正在寻找合适的算法来比较两个文件。diff我认为我可以比由于一些额外的限制做得更好。

我拥有的是两个文本文件，每个文件都包含一个文件列表。它们是在两个不同时间拍摄的系统上所有文件的快照。我想弄清楚在两个快照之间添加或删除了哪些文件。

我可以diff用来比较这些文件，但我不想这样做，因为：

1. diff尝试将更改组合在一起，查找文件中的哪些块已更改。我只是在寻找一个已经改变的行列表，这应该比找到最长的公共子序列或类似的东西要简单得多。

2. 广义差异算法在运行时或空间上是O(mn) 。我正在寻找更像时间上的O(m+n)和空间上的O(1)的东西。

以下是该问题的限制条件：

1. 两个文件中的文件列表顺序相同。它们不一定按字母顺序排列，但它们的相对顺序相同。

2. 大多数情况下，列表之间不会有任何差异。如果存在差异，通常只会有少数新/删除的文件。

3. 我不需要将结果组合在一起，比如说“整个目录已被删除”或“第 100-200 行是新的”。我可以单独列出不同的每一行。

我认为这相当于拥有两个排序列表并试图找出两个列表之间的差异的问题。问题是列表项不一定按字母顺序排序，因此您不知道一项是否比另一项“更大”。您只知道两个列表中存在的文件的顺序相同。

对于它的价值，我几年前曾在Ask Metafilter上发布过这个问题。请允许我预先回答几个可能的答案。

答：这个问题称为最长公共子序列。

回应：我试图避免最长的公共子序列，因为简单的算法在O(mn)时间/空间中运行，而更好的算法更复杂且更“启发式”。我的直觉告诉我，由于添加了约束，所以存在线性时间算法。

答：按字母顺序排列，然后比较。

响应：那将是O(m log m+n log n)，这比O(m+n)差。

我已经看到一些关于 SO re Java hashmaps 及其O(1)查找时间的有趣声明。有人可以解释为什么会这样吗？除非这些哈希图与我购买的任何哈希算法有很大不同，否则必须始终存在包含冲突的数据集。

在这种情况下，查找将是O(n)而不是O(1).

有人可以解释他们是否是O(1)，如果是，他们是如何实现的？