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

概述有谁知道在 ruby中使用( Merge)函数合并两个哈希的时间复杂度是多少？ 在我看来,它将是O(n ^ 2),因为对于散列h1中的每个元素,应该检查h2中的所有元素,如果两个散列中的两个元素具有相同的值,则其中一个的键值应该是改变了. 我不确定我的假设是否正确.任何人都可以帮我找出合并哈希的时间复杂度吗？ 您的假设是错误的,因为无需检查h1和h2是否有任何重复键. merge method声明 有谁知道在 ruby中使用( Merge)函数合并两个哈希的时间复杂度是多少？

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

我不确定我的假设是否正确.任何人都可以帮我找出合并哈希的时间复杂度吗？

解决方法 您的假设是错误的,因为无需检查h1和h2是否有任何重复键. merge method声明重复键将默认为h2中的值.

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

检查合并方法上的源会产生以下代码

static VALUErb_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 – 合并两个哈希的时间复杂度全部内容，希望文章能够帮你解决ruby – 合并两个哈希的时间复杂度所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。