ruby - 我的代码的 Big-O 复杂度是多少？

Question

给定一个整数数组，编写一个方法返回所有加起来为 100 的唯一对。

示例数据:

sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]]

这个周末我正在解决这个问题，虽然我的解决方案看起来可扩展且高效，但我想确定我的解决方案在最坏情况下的时间复杂度是多少？

这是我的解决方案:

def solution(arr)
  res = []
  h = Hash.new

  # this seems to be O(N)
  arr.each do |elem|
    h[elem] = true
  end

  # how do I determine what Time complexity of this could be?
  arr.each do |elem|
    if h[100-elem]
      h[100-elem] = false
      h[elem] = false
      res << [elem, 100-elem]
    end
  end
  res 
end

如果两个循环都是 O(N)，我将它们加起来:O(N + N)，这将等于 O(2N) 并将 2 设为常数，我可以假设我的解决方案是 O (N)？

Answer 1

你是对的。如果考虑散列搜索/插入的分摊运行时间，此代码的大 O 将为 O(n)。

如果您采用哈希搜索/插入的真实最坏情况 (O(n))，则它将是 O(n^2)。

See Wikipedia on Hash Tables