Ruby中的复杂性= =

发布时间：2020-12-17 02:08:47 所属栏目：百科来源：网络整理

导读：此操作的复杂性(Big O)是多少： my_array | = [new_element] 它是O(n),因为它需要通过现有的数组检查new_element是否存在？解决方法让我们来看看Wand Maker的评论. 看一眼 http://ruby-doc.org/core-2.2.3/Array.html#method-i-7C https://github.com/ruby

此操作的复杂性(Big O)是多少：

my_array | = [new_element]

它是O(n),因为它需要通过现有的数组检查new_element是否存在？

解决方法

让我们来看看Wand Maker的评论.
看一眼

> http://ruby-doc.org/core-2.2.3/Array.html#method-i-7C
> https://github.com/ruby/ruby/blob/trunk/array.c

rb_ary_or的来源

static VALUE
rb_ary_or(VALUE ary1,VALUE ary2)
{
    VALUE hash,ary3;
    long i;

    ary2 = to_ary(ary2);
    hash = ary_make_hash(ary1);

    for (i=0; i<RARRAY_LEN(ary2); i++) {
        VALUE elt = RARRAY_AREF(ary2,i);
        if (!st_update(RHASH_TBL_RAW(hash),(st_data_t)elt,ary_hash_orset,(st_data_t)elt)) {
            RB_OBJ_WRITTEN(hash,Qundef,elt);
        }
    }
    ary3 = rb_hash_values(hash);
    ary_recycle_hash(hash);
    return ary3;
}

我会说你的问题的答案是“是”(充其量 – 参考@cliffordheath的评论)“,因为看起来我们对于ary_make_hash(芳基)有O(n1)而对于for循环有O(n2).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!