ArrayList, содержащий ссылки на TreeNodes, какова сложность пространства?

   TreeNode root = new TreeNode(5);
    ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
    for(int i = 0; i < n; i++){
        arr.add(root);
    }

В приведенном выше коде, один TreeNode объект добавлен в ArrayList<TreeNode> arr для п раз. я думаю что arr должен иметь космическую сложность O(1) потому что он сохраняет ссылки на один блок памяти в куче. Я обсуждаю это с моими друзьями, и у них другое мнение, что это может иметь O(n) сложность. Что, вы парни, думаете?

Источник

2 ответа

Решение

Вы сохраняете ссылки, но они по-прежнему n ссылок. Я думаю, что вы на самом деле ищете накладные расходы памяти для хранения n объектов в ArrayList, В используемой памяти, вероятно, будут преобладать реальные объекты, но все еще существует массив с длиной n, который поддерживает ArrayList проведение ссылок.

Источник

ArrayList все еще должен хранить ссылку n раз, делая ее O (n).

ArrayList поддерживается Object[], если вы посмотрите на исходный код

public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

Всякий раз, когда элемент добавляется, он добавляется в массив объектов поддержки.

Источник
Другие вопросы по тегам