两个散列合并的时间复杂性

Question

有人知道在ruby中使用（Merge）函数合并两个散列的时间复杂度是多少吗？

在我看来，它将是O（n^2），因为对于哈希h1中的每个元素，h2中的所有元素都应该被检查，如果两个哈希中的两个元素具有相同的值，则其中一个元素的键值应该被更改。

我不确定我的假设是否正确。有人能帮我了解合并哈希的时间复杂性吗？

Answer 1

您的假设是错误的，因为不需要检查h1和h2是否有任何重复的密钥。merge方法声明重复键将默认为h2中的值。

至于真正的答案。。。你需要挖一点。

在merge方法上检查源产生以下代码

static VALUE
rb_hash_merge(VALUE hash1, VALUE hash2)
{
    return rb_hash_update(rb_obj_dup(hash1), hash2);
}

所以继续前进。rb_hash_update的Ruby源代码是这个

rb_hash_update(VALUE hash1, VALUE hash2)
{
    rb_hash_modify(hash1);
    hash2 = to_hash(hash2);
    if (rb_block_given_p()) {
        rb_hash_foreach(hash2, rb_hash_update_block_i, hash1);
    }
    else {
        rb_hash_foreach(hash2, rb_hash_update_i, hash1);
    }
    return hash1;
}

最后是rb_hash_foreach源

rb_hash_foreach(VALUE hash, int (*func)(ANYARGS), VALUE farg)
{
    struct hash_foreach_arg arg;
    if (!RHASH(hash)->ntbl)
        return;
    RHASH_ITER_LEV(hash)++;
    arg.hash = hash;
    arg.func = (rb_foreach_func *)func;
    arg.arg  = farg;
    rb_ensure(hash_foreach_call, (VALUE)&arg, hash_foreach_ensure, hash);
}

散列之间的一次迭代产生O（n）。

Answer 2

你的有理数得到O（n^2）是没有意义的。这最多是一个O（n+m）运算，其中n == h1.keys.length和m == h2.keys.length

以下是我如何编写合并操作：

• O（n）：创建一个内容为h1:h_new = h1.dup的新哈希
  • 假设我们需要从h1循环到dup（可能是非最优解决方案）
• O（m）：在h2:h2.keys.each { }中的密钥上迭代
  • 循环中的每个键，插入h_new[key] = h2[key]

因此，上面的算法产生了一个O（n+m）的结果。

Answer 3

将元素添加到Hash具有O（n）的渐近最坏情况步长复杂度，但具有O（1）的渐近摊余最坏情况阶复杂度。合并与将第二个Hash的所有元素添加到第一个Hash相同，因此它具有O（n²）的渐近最坏情况步长复杂度，但具有O（n）的渐近摊余最坏情况步骤复杂度。

Answer 4

对于hashh1中的每个元素，都应该检查h2中的所有元素如果两个散列中的两个元素具有相同的值，则键值其中一个应该更改。

有一种不那么复杂的方法可以实现这一点：

h1 = {
  a: 1,
  b: 2,
  c: 3,
}
h2 = {
  a: 'hello',
  d: 4,
}
results = {}
h1.each do |key, val| 
  results[key] = val
end
h2.each do |key, val| 
  results[key] = val
end
p results
p h1.merge h2
--output:--
{:a=>"hello", :b=>2, :c=>3, :d=>4}
{:a=>"hello", :b=>2, :c=>3, :d=>4}

所以O(n)。