时间戳

首页 > 解决方案 > Is this kata solution considered O(n)?

ruby - Is this kata solution considered O(n)?

问题描述

I have the following solution to a kata:

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)

I'm relearning BigO notation and doing some job interview katas. From what I've learned so far, I would say that this implementation is O(n) notation which is considered "fair". Is this a correct assumption? I say that this is O(n) because I have one loop, the .each. The bigger the array gets the longer it would take. This to me implies a linear O. However, the .include? is throwing me off. I don't know how the internals of .include? works. Does it even matter? Am I indeed correct to say that this is O(n)? Confirmation would be appreciated. Thanks.

标签： rubyalgorithm

解决方案

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

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

推荐阅读