ruby - 这个kata解决方案是否被认为是O(n)？

Question

我对一个型有以下解决方案:

def commonalities(array1, array2)
  in_common = false
    array1.each do |elem|
      if array2.include?(elem)
        in_common = true
        break
      end
    end
  puts in_common
end


##### Problem: Should find common elements in an array 

array1 = ['a','b','c','x']
array2 = ['z','y','i']
commonalities(array1, array2)
# return false
array1 = ['a','b','c','x']
array2 = ['z','y','x']
# return true
commonalities(array1, array2)

我正在重新学习 BigO 符号并做一些工作面试套路。根据我目前所学，我会说这个实现是 O(n) 表示法，被认为是“公平的”。这是一个正确的假设吗？我说这是 O(n)，因为我有一个循环，.each。阵列越大，所需的时间就越长。这对我来说意味着线性 O。但是，.include? 让我失望了。我不知道 .include? 的内部结构是如何工作的。这有关系吗？我说这是 O(n) 确实正确吗？确认将不胜感激。谢谢。

Answer 1

.include? 的内部实现很重要，因为它可能是另一个 for 或 each 循环，因此更接近 O(mn).

如果您知道，例如array1 保证是一个常数大小，您可以说它是 O(n)，其中 n 是另一个数组的长度。然而，在这类问题中，我们通常假设两个数组的长度都是可变的，所以这个实现会被认为是 O(mn)，或者 O(n ²) 如果已知两个列表具有相同的长度。