Почему ArrayList.remove(i) в цикле ведёт к квадратичному времени выполнения?

339

25 сентября 2017, 01:39

На вопрос удаление каждого К-того элемента из arraylist по кругу был предложен ответ:

import java.util.ArrayList;
public class MyClass {
    public static void main(String[] args) {
        ArrayList <Integer> list1 = new ArrayList();
        int n = 10;
        int k = 3;
        for (int i = 0; i<n; i++){
            list1.add(i+1);
        }
        int pos =0;
        while (list1.size()!=1)
        {
            pos = (pos+k-1)%list1.size();
            list1.remove(pos);
        }
        System.out.print(list1.get(0));
    }
}

Это квадратичный алгоритм O(n²), но по-видимому это не очевидно, так как приводит к вопросам:

... где вы тут n^2 увидели? ... тут один цикл while, который за каждую итерацию "убирает" по одному элементу, где здесь квадрат?

Как себя ведут популярные реализации Java? Гарантирует ли спецификация языка O(n) поведение для ArrayList.remove(i) для произвольного индекса?

Answer 1

Хороший вопрос, сейчас объясню, в чем здесь дело. Дело в том, что реализация коллекции ArrayList основана на массиве. А как известно, под массив память выделяется блоками, таким образом доступ к элементу осуществляется за константное время - просто по его индексу. И можно было бы на этом закончить, если бы не одно НО.
При удалении элемента из ArrayList происходит сдвиг всех элементов после идекса удяляемого элемента в массиве на одну позицию левее. Сейчас поясню на примере. Исходный массив:

[1, 2, 3, 4, 5, 6]

Мы делаем .remove(3) и получаем такое состояние:

[1, 2, 4, 5, 6, 6]

После чего последний индекс массива (последняя цифра 6) зануляется.
Сдвиг осуществляется посредством нативного метода System.arrayCopy(), который написан не на Java и работает в разы быстрее обычного ручного поэлементного копирования, тем не менее скорость его работы в нотации Big O оценивается близкой к O(n).

Для случая с LinkedList, который основан на двусвязном списке, хоть мы и удаляем по индексу, в любом случае нам необходимо найти этот элемент прежде, чем удалить, а это обычный поиск линейной сложности O(n)