Комментарии 11
А почему при вставке массив увеличивается в 2 раза? Почему бы просто не добавить один элемент? Зачем такая расточительность по памяти?
привет, хороший вопрос я предполагаю потому что увеличение массива достаточно трудоемкий процесс, ведь нужно копировать каждый элемент O(n), поэтому решили каждый раз делать с запасом, чтобы при следущей вставки в конец(append) скорость была O(1).
Но ведь когда эта навая часть закончится, снова будет вставка за O(n). почему, например, не добавлить 10 или 100 элементов? Зачем удваивать массив каждый раз, когда он кончается?
Ну так в том и суть, что массив не переаллоцирует буффер при каждой вставке, а это делается периодически, все реже и реже. Если переаллоцировать на каждой вставке, то это будет очень неэффективно. Чем больше массив, тем медленней растет внутренний буффер. Увеличение в 2 раза — оптимальное количество, поскольку неизвестно, насколько массив еще вырастет. Сложность у такого алгорима хоть и не чистая O(n), но близкая. Подробней про это можно почитать в википедии: Динамический массив.
Сложность у такого алгорима хоть и не чистая O(n), но близкая.
Ниже t-nick уже объяснил, что при мультипликативном увеличении размера массива, добавление работает за O(1) в амортизационно.
Я, правда, надеялся что автор про это расскажет.
спасибо за ссылку, добавлю в статью
Если увеличивать размер на константу k, то средняя сложность добавления элемента будет O(n), при n >> k, (n * n / k) / n = n / k. При удвоении размера, в среднем будет O(1), так как копироваться будет n элементов на каждое 2n добавление, (n + 2n) / n = 3, то есть константное время. То есть большое время копирования компенсируется намного меньшим временем добавления остальных элементов в цикле.
Не эксперт в оценке сложности алгоритмов, но примерно так.
Как работает массив в Swift