arrays - 判断两个数组是否相等 - 在不对数据做任何假设的情况下 O(n) 是否可能？

Question

我一直想知道判断两个无序 数组是否由相同元素组成的最坏情况下的时间复杂度。元素可以是任何类型。数字、字符串、自定义对象...等等，但我们假设元素既可排序又可散列。

我想到了三种方法，在 this stackoverflow post 中有很好的解释。 .哪些是 1) 使用散列 2) 使用排序 3) 只是循环。

帖子说，如果数据是可散列的，则有可能实现最坏时间 O(n)，但是，我认为这不太正确，因为在 Hash 中插入和搜索并不是最坏的-case O(1) 操作。如果没有发生碰撞，平均是 O(1)，但插入和搜索(理论上)都是 O(n)。因此，如果发生大量冲突，使用散列来判断两个数组是否相等将花费 O(n^2)。 (如有错误请指正。)

所以在我看来，判断两个数组是否相等所花费的成本与对数组进行排序的成本一样高，在不了解数组的情况下，这将花费 O(nlogn)。 (假设比较两个相等的元素总是花费 O(1))

是否有可能在最坏的 O(n) 情况下判断两个数组相等？我将不胜感激任何评论、重复的标记、对论文的引用。谢谢!

这是我比较两个数组是否相等的代码。 (它在 ruby​​ 中并且可以工作，但请更像是伪代码)

一个。通过散列比较 - 平均 O(n)，最坏情况 O(n^2)

def compare_by_hashing(list1, list2)  
  hash1 = {}  
  list1.each do |item|  
    hash1[item] ||= 0  
    hash1[item] += 1  
  end  
  hash2 = {}  
  list2.each do |item|  
    hash2[item] ||= 0  
    hash2[item] += 1  
  end  

  hash1.each do |key, hash_1_value|  
    return false if hash_1_value != hash2[key]  
  end  
  return true  
end  

两个。通过排序进行比较。最坏情况 O(nlogn)

# 2. compare by sorting. Worst-case `O(nlogn)`
def compare_by_sorting(list1, list2)  
  list1.sort  
  list2.sort  

  list1.each_with_index do |list_1_item, index|  
    return false if list_1_item != list2[index]  
  end  
  return true  
end  

三个。通过循环比较。最坏情况 O(n^2)

def compare_by_looping(list1, list2)  
  list1.each do |item|  
    if list2.include? item  
      list2.delete item  
    else  
      return false  
    end  
  end  
  return true  
end  

编辑

我很欣赏并理解散列运算通常会显示 O(1) 时间复杂度并且最坏情况不太可能发生的答案和评论。然而，由于它们无论如何都可能发生，我不想忽视这些可能性。我很抱歉没有表达清楚我的观点。我的第一个意图是找到理论上证明的 O(n) 算法，不是 实用算法。 感谢您的关注。我真的很感激。

Answer 1

是的，您可以使用散列。

如果散列函数对数据集来说真的很糟糕，那么你会在散列中遇到冲突，如果散列函数是常量(总是返回 1 或类似的东西)，你可能只会得到 O(N^2)。

实际上，您可以使用加密散列函数，并且可以相当确定您不会遇到太多散列冲突。这是因为没有人可以故意生成具有相同 SHA-1 哈希值的输入(很多人都在尝试)。或者尝试一个完美的哈希算法。

所以你的最坏情况分析是基于错误的假设。使用良好的散列函数可确保您始终接近平均情况，而绝不会出现最坏情况。