ADTs List и Iterator

Question

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

Answer 1

• Добавлен 1-й элемент. (1 операция).
• Добавлен второй элемент. Скопируйте 1-й элемент и добавьте новый (2 операции).
• Добавлен третий элемент. Скопируйте 1-й и 2-й элементы и добавьте новый (3 операции)
• n-й элемент. Скопируйте (n-1) и добавьте новый (n операций).

Таким образом, для добавления п элементов мы имеем в общей сложности 1 + 2 + 3 + ... + п операций, which is equal to (п) (п + 1)/2 = (п^2 + N)/2. В Big O Notation можно сказать, что добавление элементов в эту коллекцию O (n^2).