Алгоритмы и структуры данных. Извлечение информации на языке Java

3

Класс ArrayList

Эта глава убивает сразу двух зайцев: я объясняю решение

предыдущего упражнения и демонстрирую способ классифи-

кации алгоритмов с помощью амортизационного анализа.

Классификация методов MyArrayList

Для многих методов можно определить порядок роста, изучая

код. Например, ниже представлена реализация метода get из

MyArrayList:

public E get(int index) {

if (index < 0 || index >= size) {

throw new IndexOutOfBoundsException();

}

return array[index];

}

Все в данном методе выполняется за постоянное время, поэтому

и сам он является методом постоянного времени. Нет проблем.

41

Классификация методов MyArrayList

Теперь, когда мы классифицировали get, можно то же проде-

лать с методом set, который его использует. Наша реализация

set из предыдущего ...