问题标签 [time-complexity]

我目前正在为 iPhone 开发一个项目，该项目需要访问存储在本地 sqlite 数据库中的大量分层数据。更常见的操作之一是计算汇总状态字段。现在，我通过递归遍历该项目的所有后代（可以是 1 到 n 层深的任何地方）来做到这一点。然而，这最终需要大量的 sql 调用。iPhone 上的每个 sqlite 调用大约需要 250 毫秒才能完成，最后这加起来大约需要 7.7 秒的处理时间。有没有人有任何建议在少于 O(n) 的时间内做这样的事情？我认为问题的根源在于正在进行的大量 sql 调用，所以这就是我想要减少的。

有人可以向我解释如何确定算法的最坏情况复杂性。我知道我们需要使用方程 W(n) = max{t(I)|I 的 D 元素)，其中 D 是大小为 n 的输入集。我是否计算为每个元​​素执行的操作次数，然后取其最大值？有什么更简单的方法可以做到这一点？

正如标题所问，我想知道 LinkedList 类中的 size() 方法是否需要分摊的 O(1) 时间或 O(n) 时间。

我需要一个 dotnet 中的数据结构，我可以在恒定时间内搜索一个项目。这意味着数据结构应该在内部实现索引。字典用于此目的还是其他目的？

我试图在创建的几个算法上获得最差的运行时复杂度顺序。但是，我遇到了一个问题，即我一直倾向于为算法选择错误或错误数量的基本操作。

在我看来，基本操作的选择更像是一门艺术而不是一门科学。在谷歌搜索和阅读我的文本框后，我仍然没有找到一个好的定义。到目前为止，我已将其定义为“始终在算法执行中发生的操作”，例如比较或数组操作。

但是算法通常有许多总是执行的比较，所以你选择哪个操作？

我正在浏览一些数据结构，我注意到这是一个时间复杂度： O(log(log(n))))-competitive。

我读到持续竞争是预期时间/最佳时间的比率。但是，有一个集合竞争意味着什么？

我正在尝试评估一些基本图像过滤算法的复杂性。我想知道你是否可以验证这个理论；

对于像 Inverse 这样的基本逐像素过滤器，操作的数量随着输入的大小（以像素为单位）线性增长，并且

令 S = 图像边长令 M = # 像素输入

逆序为 O(M) 或 O(S^2)。

另一方面，卷积滤波器有一个参数 R，它决定了在为每个滤波器建立下一个像素值时要卷积的邻域的大小。

设 R = 卷积滤波器的半径

卷积顺序为 O(M*((R+R*2)^2) = O(M*(4R^2) = O(MR^2)

或者我应该让 N = 卷积滤波器（邻域）的大小（以像素为单位）？

O(M*(N)) = O(MN)

最终，卷积滤波器线性依赖于像素数和邻域中像素数的乘积。

如果您有任何指向已记录该文件的论文的链接，我们将不胜感激。

亲切的问候，

加文

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

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

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

谁能给我一个包含主要Java数据结构摘要的网站的参考资料，以及它们各自的时间复杂性（对于某些给定的操作，如添加、查找、删除），例如Hashtables是O（1）查找，而LinkedLists在...上）。像内存使用这样的一些细节也会很好。

这对于思考算法的数据结构非常有帮助。

可能重复：
是否有任何 O(1/n) 算法？

您的代码是否有可能是 Big O 小于 O(1)？