如何确定Big O比较Ruby中的两个数组

平均为O(n m)

最糟糕的情况是O(nm),但只有在你真的想要实现它时才会发生(参见最后一段).

如果选择array_one大于array_two,则O(m n)只是O(n),因此该算法平均以线性时间运行.

替代

另一种更简短的检查方法是：

one = [1,3]

puts Set[*one] == Set[*two] #=> true
# or
puts one.to_set == two.to_set #=> true

小重构

return true if x
return false

等同于

x

所以你的代码可以写成：

def same_elements?(array_one,array_two)
  (array_one - array_two).empty? && (array_two - array_one).empty?
end

基准

我用1E6元素创建了一个数组,其中一半是0到199999之间的随机数(用于碰撞),另一半是纯Ruby对象.

另一个数组就是第一个,随机洗牌.

N = 1_000_000

one = (1..N).map{rand < 0.5 ? rand(N/5) : Object.new}
two = one.sort_by{rand}

比较集合需要1分钟,而设置比较的fruity报告比OP的方法快20％.

对于较小的整数数组,OP的方法要快一些.

注意：@engineersmnky在评论中提出的代码报告速度与其他方法相似.

时间复杂

当与通常的阵列一起使用时,你的代码肯定不是O(nm).

大概时间是：

1E4> 1s
1E5> 8s
1E6> 160s

看看array.c中的rb_ary_diff,难怪上面描述的所有方法都在同一时间运行：它们的工作方式基本相同.

rb_ary_diff为array_two(在O(m)中)创建一个哈希表,并迭代遍历array_one的每个元素(在O(n)中),查找哈希表中的值(平均为O(1)).整个操作平均为O(n m).

blog post分析了set intersection,它以非常类似的方式实现.

两次这样做不会改变任何东西,因此整体时间复杂度保持为O(n m).

寻找O(mn)

制作此算法O(mn)的一种方法是完全禁用散列方法.除了证明这是一个非常糟糕的主意之外,没有理由这样做.

使用10_000个KeyObjects：

class KeyObject < Object
end

集合比较不到1秒.

使用10_000个KeyObjects：

class KeyObject < Object
  def hash
    1
  end
end

集合比较需要超过14分钟！

2个不同的随机Ruby对象具有相同散列的概率大约是1E-20.严格来说,这个算法的最坏情况是O(mn),但是如果你不去寻找它就永远不会发生.找到与2个元素的碰撞并非易事,找到与1E6元素的碰撞不会偶然发生.