问题标签 [time-complexity]

我正在尝试建立分布式文件系统中文件可用性的数学模型。我在 MathOverflow 上发布了这个问题，但这也可能被归类为 CS 问题，所以我也在这里试一试。

系统是这样工作的：一个节点在 r*b 个远程节点上存储一个文件（使用纠删码编码），其中 r 是复制因子，b 是一个整数常量。纠删码文件的特性是，如果至少有 b 个远程节点可用并返回文件的一部分，则可以恢复文件。

最简单的方法是假设所有远程节点彼此独立并且具有相同的可用性 p。有了这些假设，文件的可用性遵循二项分布，即

不幸的是，这两个假设可能会引入不可忽略的错误，如本文所示：http ://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf 。

克服所有节点具有相同可用性的假设的一种方法是计算可用/不可用节点的每个可能组合的概率，并取所有这些结果的总和（这是他们在上面的论文中建议的那种，只是比我刚才描述的更正式）。您可以将此方法视为深度为 r*b 的二叉树，每个叶子都是可用/不可用节点的一种可能组合。文件的可用性与您在 >=b 个可用节点的情况下到达休假的概率相同。这种方法更正确，但计算成本为. 此外，它不处理节点独立性的假设。

你们有什么好的近似值的想法，它比二项式分布近似引入更少的误差，但计算成本比 更好？

您可以假设每个节点的可用性数据是一组由 组成的元组(measurement-date, node measuring, node being measured, succes/failure-bit)。例如，您可以使用此数据计算节点之间的可用性与可用性差异的相关性。

曾经听过下面一段话，但忘记了是谁写的：

在等待（多项式时间）算法停止时，不要忘记您的生命周期也受到多项式的限制。

有人可以提供参考吗？

我的另一个问题是：多项式时间算法很棒，但是在实践中使用的算法的一个例子是什么，它需要O(n^101)，即受一个高次多项式的限制？

这个问题一直萦绕在我的脑海中……

假设我有一个项目列表和它们的等价关系，并且比较两个项目需要恒定的时间。我想返回项目的一个分区，例如一个链表列表，每个链表都包含所有等效项目。

这样做的一种方法是将等价扩展到对项目的排序并对其进行排序（使用排序算法）；那么所有等效的项目将是相邻的。

但它可以比排序更有效吗？这个问题的时间复杂度比排序低吗？如果不是，为什么不呢？

是HashSet.ElementAtO(1) 中的实现吗？如果不是，它是什么？

有一个博物馆组织为 NxN 房间。部分房间上锁且无法进入。其他房间是开放的，有些房间有警卫。守卫只能通过开放的房间和博物馆内的南北东和西移动。对于每个房间，找出到警卫的最短距离。你的算法的时间复杂度是多少？

我在试图掌握大 O 表示法的概念时遇到了一些问题。因此，根据定义，大 O 如下，T(n) ∈ O(G(n)) if T(n) <= G(n) * C。

由于常数“C”可以是任何大于 0 的整数，所以下面的例子不也是真的吗？

例子：

其中 C 等于 n 的值。

我知道答案是这样，n log n ∉ O(log n)但我不明白为什么 C 可以是任何常数。

提前感谢您的帮助：D

我知道有一个最坏情况 O(n log n) 算法可以找到复杂多边形的凸包，还有一个最坏情况 O(n) 算法可以找到简单多边形的凸包。是否存在用于查找复杂多边形的凸包的最坏情况 O(n) 算法？

复杂多边形是线段可能相交的多边形。找到一个复杂多边形的凸包相当于找到一个无序列点列表的凸包。

此代码a[i,j]与a[j,i]for交换的时间复杂度是多少j > i（转置给定矩阵）：

为了

是

我尝试将两者除以 n，我得到了

但我仍然不知道哪个增长更快。有人可以帮我解决这个问题并解释答案的原因吗？我真的很想知道（没有计算器）如何确定哪一个增长得更快。

这是一个非常有名的跨国公司问我的问题。问题如下...

输入 0 和 1 的 2D N*N 数组。如果 A(i,j) = 1，则第 i 行第 j 列对应的所有值都将为 1。如果已经有 1，则保持为 1。

例如，如果我们有数组

我们应该得到输出

输入矩阵是稀疏填充的。

这可能在小于 O(N^2) 的时间内完成吗？

没有提供额外的空间是另一个条件。我想知道是否有一种方法可以使用空间 <= O(N) 来实现复杂性。

PS：我不需要复杂度为 O(N*N) 的答案。这不是家庭作业问题。我已经尝试了很多，但无法找到合适的解决方案，并认为我可以在这里得到一些想法。将打印放在一边以考虑复杂性

我的粗略想法是可以动态消除遍历的元素数量，将它们限制在 2N 左右。但我无法得到一个正确的想法。