代码之家 › 专栏 › 技术社区 › Dan Rubio

这个kata解被认为是o(n)吗?

algorithm ruby

0

Dan Rubio · 技术社区 · 6 年前

我有以下关于卡塔的解决方案:

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符号,并做一些工作面试katas。从我目前所了解到的情况来看,我认为这个实现是O(N)符号,被认为是“公平的”。这是正确的假设吗?我说这是o(n),因为我有一个循环 .each . 阵列越大,所需时间越长。这对我来说意味着一个线性的o。 .include? 把我甩了。我不知道 包括? 作品。这有关系吗?我说这是o(n)真的正确吗?请确认。谢谢。

3 回复 | 直到 6 年前

1

ruakh 6 年前

内部实施 .include? 很重要,因为这很可能是另一个 for 或 each 环,离o很近( 锰 )

如果你知道e.g.array1被保证为恒定大小,你可以说它是o( n 在哪里 n 是另一个数组的长度。然而,在这类问题中,我们通常假设两个数组的长度都是可变的,所以这个实现可以看作是( 锰 ),或作为O( n ^二 )如果两个列表的长度相同。

2

0

Morrison Cole 6 年前

记住'n'只是描述一些输入的大小。在您的示例中,有两个输入 (array1, array2) .

循环过度 array1 可以说是 O(n) 其中n是数组的大小。

但是呢 array2 ?它的大小如何影响算法的运行时间?它是一个数组,所以运行contains操作也是线性的。

你看的是 O(nm) .

3

0

Maras 6 年前

如果数组没有被排序,则证明没有比o(n logn)更快的算法。

对于array1中的每个元素,检查它是否出现在array2中。所以你的电脑一定知道答案。

看。包括?实现可以很容易地看到它遍历array2并检查元素。

       VALUE
       rb_ary_includes(VALUE ary, VALUE item)
       {
            long i;
            VALUE e;

             for (i=0; i<RARRAY_LEN(ary); i++) {
             e = RARRAY_AREF(ary, i);
             if (rb_equal(e, item)) {
                  return Qtrue;
              }
         }
         return Qfalse;
        }

这个函数的一个调用就是o(n)。这就是为什么你的算法复杂度是o(n^2)

(好吧,o(n m)更正确,其中n是数组1的长度,m是数组2的长度)