如何确定Ruby中数组差异的大O时间复杂度

Question

如何确定 Ruby 中数组差异的大 O 时间复杂度？

例如：

array_1 = [1,2,3]
array_2 = [5,4,3,2,1]

array_2 - array_1 #gives [5,4]

它是如何array_2 - array_1工作的以及它的时间复杂度是多少？

Answer 1

我的问题是如何array_2 - array_1运作

Ruby 规范没有规定任何特定的实现方式Array#-。它仅规定了结果。因此，任何 Ruby 实现者都可以自由地实现Array#-他们想要的方式，并且可以出于任何原因随时更改其实现。

它的时间复杂度是多少？

Ruby 规范没有规定任何特定的时间复杂度Array#-。它仅规定了结果。因此，任何 Ruby 实现者都可以自由地实现Array#-他们想要的任何时间复杂度，并且他们可以出于任何原因随时更改时间复杂度。

以 O(n) 的预期步骤复杂度执行集合差分是很容易的，甚至可能，但更复杂，对于集合中值的分布的某些假设以亚线性步骤执行，即比 O 更好（n）。我猜大多数实现者会选择更简单的 O(n) 解决方案，但不能保证这一点。如果您想知道特定实现的特定版本如何针对特定的元素分布执行操作，那么您必须查看该特定实现的特定版本的源代码。但是，请注意，不能保证其他实现甚至同一实现的其他版本也会以相同的方式执行此操作。

举个例子：Rubinius 最初使用的实现Hash与 YARV 使用的实现非常相似，但后来他们改用了基于哈希数组映射尝试的实现。因此，根据您使用的 Rubinius 版本，Hashes 可能会使用完全不同的算法来实现。事实上，在过渡期间，Rubinius 提供了旧的和新的实现，您可以使用命令行选项在两者之间切换。

举个例子，下面是Rubinius的当前实现Array#-：

def -(other)
  other = Rubinius::Type.coerce_to other, Array, :to_ary

  array = []
  im = Rubinius::IdentityMap.from other

  each { |x| array << x unless im.include? x }

  array
end

正如您所看到的，对于这个特定版本的 Rubinius， 的步骤复杂度a - b是 θ(|a| + |b|)。但让我重申一下：这只适用于这个特定版本的 Rubinius。其他版本的 Rubinius 或其他 Ruby 实现可能（而且几乎肯定）有不同的实现。

我假设你是 C++ 程序员对吗？C++ 库规范相当特殊，因为它实际上规定了算法的复杂性，并且实现者必须实现满足这些复杂性的算法。Ruby 的情况并非如此，事实上，大多数其他语言也是如此。