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

Question

我的算法技巧很黯淡.我创建了一个方法来查看两个数组是否包含相同的元素(重复无关紧要):

one = [1, "taco", 3, 2, :piece, 4, 5, 5, 5, 5]
two = [:piece, 2, 5, 4, 1, "taco", 3]

def same_elements?(array_one, array_two)
  return true if ( (array_one - array_two).empty? && (array_two - array_one).empty? )
  return false
end

same_elements?(one, two)

这返回true(这是正确的).问题是,我不确定这个算法的效率是多少.我的第一个猜测是O(n ^ 2)因为我们必须检查ab和ba.我知道O(n ^ 2)非常可怕.有没有更有效的方法来做到这一点？

Answer 1

简短的回答

平均为O(n + m)

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

如果array_one选择大于array_two,O(m + n)只是O(n),那么该算法平均在线性时间内运行.

替代

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

one = [1, "taco", 3, 2, :piece, 4, 5, 5, 5, 5]
two = [:piece, 2, 5, 4, 1, "taco", 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分钟,设置比较的果味报告比OP的方法快20%左右.

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

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

时间复杂

当您使用常规阵列时,您的代码肯定不会 O(nm).

大概时间是:

• 1E4的1s
• 8E为1E5
• 160年代的1E6

在展望rb_ary_diff中array.c,这也难怪上面运行的同时所描述的所有方法:他们基本的工作方式相同.

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

这篇博客文章分析了集合交集,它以非常类似的方式实现.

这样做两次不会改变任何东西,因此整体时间复杂度保持为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元素的碰撞不会偶然发生.