Как определить сложность программы в Big-O при добавлении в полный ArrayList?

Question

Я прохожу практический экзамен на уроке информатики.Однако я не уверен в следующем вопросе.

Рассмотрим четыре различных подхода к изменению размера структуры данных списка на основе массива.В каждом случае, когда мы хотим добавить () элемент в конец массива, но он заполнен, мы создаем новый массив, а затем копируем элементы из старого в новый.Для каждого из следующих вариантов выбора размера нового массива укажите сложность добавления в конец списка в терминах big-O:

(i) увеличить размер массива на 1 элемент.

(ii) Увеличение размера массива на 100 элементов.

(iii) Удвоение размера массива.

(iv) Удвоение размера массива.

Поскольку вы вызываете один и тот же System.arraycopy() метод достижения времени независимо, разве сложность не будет одинаковой для каждого?

Answer 1

Поскольку вы вызываете один и тот же метод System.arraycopy (), время достижения независимо, разве сложность не будет одинаковой для каждого?

Да и нет.

Да - когда вы действительно делаете копию, стоимость копии будет одинаковой во всех случаях.

(Они не совсем одинаковы, если учесть стоимость выделения и инициализации массива. Требуется больше места и времени для выделения и инициализации массива 2 * N элементов, чем для N + 1 элементов. Новы будете копировать только N элементов в массив.)

Нет - различные стратегии приводят к тому, что копии массива происходят разное количество раз.Если вы выполните полный анализ сложности для последовательности операций, вы обнаружите, что варианты 3 и 4 отличаются по сложности от 1 и 2.

(И стоит отметить, что 2 будет быстрее, чем 1,даже если они имеют одинаковую сложность.)

Типичный анализ этого включает в себя вычисление общих затрат на что-то вроде этого:

List<Object> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
    list.add(new Object());
}

---

^{(Подсказка: анализ может быть приведен в качестве примера в рекомендованном вами учебнике по «структурам данных и алгоритмам» или в примечаниях к лекциям. Если это так, то это то, что вам следует пересмотреть (перед проведением практических экзаменов!) Если нет, то Googleдля «сложности амортизируемых arraylist», и вы найдете примеры.)}