Какова временная сложность retainAll и removeAll из ArrayList в Java.

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

На самом деле это зависит от реализации Коллекций c.Критическим моментом является вызов c.contains(...) в алгоритме.Вам нужно пройтись по всем вашим собственным элементам, но что происходит в том, что содержит метод?

Давайте посмотрим на лучший и наихудший случай:

Лучший случай (HashSet)

Поиск произошел в O (1) , поскольку элементы хранятся по их хеш-значениям.

Поскольку все элементы в ArrayList должны быть проверены, вы получили время выполнения O (n) ( n - размер элементов в вашем списке)

Худший случай (LinkedList)

Поиск произошел в O (м) ( m элементов в LinkedList).

Таким образом, для каждого элемента в n вам нужно найти элемент в LinkedList, который вы получите O (нм) .

Answer 2

Удаление элемента из ArrayList занимает O (N) времени, потому что вам нужно сместить все элементы после него в направлении начала, чтобы заполнить созданный вами пробел.

retainAll и removeAllОднако не используйте эту процедуру для удаления каждого элемента.Они написаны для выполнения всех необходимых сдвигов во время одного прохода через массив.

При прохождении через массив сохраняемые элементы перемещаются вперед через промежуток, созданный любыми удалениями,сдвиг промежутка к концу массива.Элементы, которые должны быть удалены, игнорируются, что приводит к увеличению разрыва.

Поскольку это занимает всего один проход через массив, независимо от того, сколько элементов вы должны удалить, эти методы также работают за O (N) время., если справочная коллекция может сделать contains() в O (1).

Answer 3

Предположим, что наш ArrayList<T> имеет n элементов, а Collection<?> имеет r элементов.

Ответ зависит от времени проверки c.contains(es[r]), как реализовано в подклассе 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)