我的代码的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(n)如果您考虑哈希搜索/插入的摊销运行时间，则此代码的 Big-O 将会是。

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

请参阅维基百科有关哈希表的内容