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

Question

据我所知它是 O(n^2) 或者是？

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

Answer 1

假设我们ArrayList<T>有n元素，并且Collection<?>有r元素。

答案取决于c.contains(es[r])检查的时间，如在 的子类中实现的Collection<?>：

• 如果c是另一个ArrayList<?>，那么复杂度实际上是二次 O(n*r)，因为c.contains(es[r])是 O(r)
• 如果c是 aTreeSet<?>那么时间复杂度就变成 O(n*log ₂ r)，因为c.contains(es[r])是 O(log ₂ r)
• 如果c是aHashSet<?>那么时间复杂度就变成O(n)，因为基于hash的c.contains(es[r])是O(1)