ruby - 计算Ruby Array#uniq自己实现的时间复杂度

Question

我看到了this .

我用不同的参数做到了这一点:

def uniq(arr)
  out = {}
  arr.each do |el|
    out[el] = nil
  end
  out.keys
end

这段代码的复杂性是多少？我该如何改进它？

更新

关于:

def uniq(arr)
  arr | []
end

Answer 1

函数的时间复杂度是 O(n)，因为它需要做的工作与数组的大小成线性比例。

您有两个循环arr.each和out.keys。每个循环体的复杂度都是O(n)，因为每个循环体的复杂度都是O(1)(即循环体内需要完成的工作是独立的)数组大小)。由于两个循环彼此独立，因此总复杂度为 O(n)。

你的第二个函数的时间复杂度也为 O(n)。它将数组转换为一个集合以消除重复项，然后将其转换回数组。要将其转换为集合，它将首先以时间复杂度 O(n) 循环遍历数组的内容；每次迭代都会将一个项目插入到集合中。将项目插入 ruby​​ Set 的时间复杂度为 O(1)(Set 使用哈希实现，哈希通常具有恒定的插入时间)。将最终集合转换回数组需要另一个循环。同样，这个循环的时间复杂度为 O(n)。 arr -> set 和 set -> arr 两个循环相互独立，因此最终的时间复杂度为 O(n)。

我建议您阅读有关时间复杂度的内容: http://en.wikipedia.org/wiki/Time_complexity