我的算法的时间复杂度是 O(n log n) 吗？

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) 的函数一起使用时，总时间是完全不同的（使用基准 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) }

Answer 1

不，是 O(n^2)。

array[0...mid_idx]（即切片）每次都会创建一个。因此，bsearch 不是 log(n)，而是 n.

此外，尝试将 bsearch 从递归方法重写为迭代方法。它工作得更快。喜欢 here.

Answer 2

您创建的算法总体上似乎是正确的。让我们试着分析一下它的复杂性。如果正确实施，您的排序应该是 O(n log n) 。现在，让我们暂时假设您的 bsearch 已正确实施（这意味着它具有复杂性 O(log n)），那么你会得到整个循环 O(n log n)。这仍然意味着算法是 O(n log n).

现在让我们开始实施bsearch。正如我所说，它通常是正确的（尽管如果您的数组具有奇数个元素，您可能应该考虑更改选择索引的部分），它失败的地方是数组切片。每当您对数组进行切片时，它都会在内部迭代切片中给出的从 start 到 end 的元素数量，并将它们复制到新数组，这打破了复杂性并使其成为 O(n) 而不是 O(log n) 从而使整个算法 O(n²), 因为循环.

我的算法的时间复杂度是 O(n log n) 吗？

Is my algorithm's time complexity O(n log n)?

ruby

algorithm

big-o

benchmarking

time-complexity