element

Question

def two_sum1?(array, value)
    array.sort! # O(nlogn)
    array.each do |element|
        return true if bsearch(array - [element], value - element) == true
    end
    return false
end

def bsearch(array, value)
    return false if array.empty?
    mid_idx = array.length / 2
    mid_value = array[mid_idx]
    return true if mid_value == value
    mid_value < value ? bsearch(array[0...mid_idx], value) : bsearch(array[mid_idx+1..-1], value)
end

我试图创建一个函数，在一个数组中找到两个唯一的数字，使它们的和等于第二个参数中的值。我相信我的实现的时间复杂度为O(n log n)。然而，当我用另一个时间复杂度也是O(n log n)的函数运行它时，使用同样的输入，总时间却大不相同（用Benchmark gem计算）。对于我的函数，它需要大约0.9秒。对于另一个函数，它需要0.003秒。我的算法分析是否有错误？我的实现是不是不符合O(n log n)？

这是另一个函数。

def two_sum2?(arr, target_sum)
  arr = arr.sort
  arr.each_with_index do |el, i|
    match_idx = arr.bsearch_index { |el2| (target_sum - el) <=> el2 }
    return true if match_idx && match_idx != i
  end
  false
end

这是我用来测试这两个函数的东西。

arr = [0, 1, 5, 7] + [100] * 10000
puts Benchmark.measure { two_sum1?(arr, 6) }
puts Benchmark.measure { two_sum1?(arr, 8) }
puts Benchmark.measure { two_sum1?(arr, 10) }
puts Benchmark.measure { two_sum2?(arr, 6) }
puts Benchmark.measure { two_sum2?(arr, 8) }
puts Benchmark.measure { two_sum2?(arr, 10) }