我试图找到重现的时间复杂性:
T(n)= 2T(n 1/2)+ log n
我非常接近解决方案,但是,我遇到了障碍.我需要解决:
n (1/2 k) = 1
为了简化我的替换模式.我不是在寻找复发的答案,只是一个解决方案k.
我试图找出 Java 中 HashMap 和 TreeMap 中 equals() 的计算复杂度。现在，您可能会说它在两种情况下都应该相同，因为 HashMap 和 TreeMap 都从 AbstractMap 继承了相同的实现。但是，在我完全接受之前，我需要一些解释。
这就是让我困惑的地方。AbstractMap 文档中覆盖的 equals() 的部分解释是：
更正式地说，如果 m1.entrySet().equals(m2.entrySet())，则两个映射 m1 和 m2 表示相同的映射。
文档不清楚 entrySet 返回的集合是 HashSet 还是 SortedSet 或其他东西。在我看来，了解这一点很重要，因为它会影响整体分析。
如果 entrySet() 返回的集合是 HashSet 类型，那么两个集合可以在 O(n) 中进行比较[在两个散列集合的情况下相等的成本]。但是，如果它们是 SortedSet 类型，那么它们可以在 O(nlogn) 中进行比较 [在两个排序集的情况下相等的成本]。因此，在 HashMap 的情况下 equals() 的复杂性在 SortedMap 的情况下会有所不同，或者至少它应该基于我的推理。
我强烈怀疑我的推理中的某个地方是错误的，所以请随时告诉我我错在哪里。什么是正确的推理。而且，最后我对 HashMap 和 SortedMap 的 equals() 的复杂性感兴趣。谢谢。