gpt4 book ai didi

ruby - 合并两个哈希的时间复杂度

转载 作者:数据小太阳 更新时间:2023-10-29 07:47:41 26 4
gpt4 key购买 nike

有谁知道在 ruby​​ 中使用 ( Merge ) 函数合并两个散列的时间复杂度是多少?

在我看来,这将是 O(n^2),因为对于散列 h1 中的每个元素,都应该检查 h2 中的所有元素,如果两个散列中的两个元素具有相同的值,则其中一个的键值他们应该改变。

我不确定我的假设是否正确。谁能帮我看看合并哈希的时间复杂度是多少?

最佳答案

您的假设是错误的,因为不需要检查h1h2 是否有任何重复键。 merge method声明重复键将默认为 h2 中的值。

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

检查 merge 方法的源代码会产生以下代码

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

所以继续。 Ruby source for rb_hash_update这是

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;
}

最后 the rb_hash_foreach source

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)。

关于ruby - 合并两个哈希的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33488940/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com