Java中ArrayList的keepAll和removeAll的时间复杂度是多少？

问题描述

据我所知它是O（n ^ 2）还是它？

As far as I can tell it is O(n^2) or is it ?

/**
     * Retains only the elements in this list that are contained in the
     * specified collection.  In other words, removes from this list all
     * of its elements that are not contained in the specified collection.
     *
     * @param c collection containing elements to be retained in this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true, 0, size);
    }

    boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {
        Objects.requireNonNull(c);
        final Object[] es = elementData;
        int r;
        // Optimize for initial run of survivors
        for (r = from;; r++) {
            if (r == end)
                return false;
            if (c.contains(es[r]) != complement)
                break;
        }
        int w = r++;
        try {
            for (Object e; r < end; r++)
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;
        } catch (Throwable ex) {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            throw ex;
        } finally {
            modCount += end - w;
            shiftTailOverGap(es, w, end);
        }
        return true;
    }

推荐答案

假设我们的 ArrayList< T> 具有 n 个元素，以及 Collection<？> 包含 r 个元素。

Assume that our ArrayList<T> has n elements, and Collection<?> has r elements.

答案取决于 c的时间安排。 [r]）支票，如 Collection<？> 的子类中实现的：

The answer depends on the timing of c.contains(es[r]) check, as implemented in the subclass of Collection<?>:

• 如果 c 是另一个 ArrayList<？> ，则复杂度为，实际上是二次O（n * r），因为 c.contains（es [r]）是O（r）


• 如果 c 是 TreeSet<？> ，则时间复杂度变为O（n * log r），因为 c.contains（es [r]）是O（log r）


• 如果 c 是 HashSet<？> ，则时间复杂度变为O（n），因为基于散列的 c.contains（es [r]）是O（1）

• If c is another ArrayList<?>, then the complexity is, indeed, quadratic O(n*r), because c.contains(es[r]) is O(r)
• If c is a TreeSet<?> then the time complexity becomes O(n*logr), because c.contains(es[r]) is O(logr)
• If c is a HashSet<?> then the time complexity becomes O(n), because hash-based c.contains(es[r]) is O(1)

这篇关于Java中ArrayList的keepAll和removeAll的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！