В письменном экзамене, я встречаю вопрос, как это:динамического массива положить элемент
Когда динамический массив заполнен, он будет распространяться на двойное пространство, это так же, как 2 до 4, 16 к 32 и т. Д. Но какая сложность заключается в том, чтобы поместить элемент в массив?
Я думаю, что расширение пространства не должно рассматриваться, поэтому я написал O(n), но я не уверен.
какой ответ?
Это зависит от вопроса, который был задан.
Если вопрос задан на время, требуемое для одной вставки, тогда ответ O (n), потому что big-O подразумевает «наихудший случай». В худшем случае вам нужно увеличить массив. Растущий массив требует выделения большего блока памяти (как вы говорите, часто в 2 раза больше, но могут использоваться другие факторы, превышающие 1), а затем копирование всего содержимого, которое является n существующими элементами. На некоторых языках, таких как Java, дополнительное пространство также должно быть инициализировано.
Если задан вопрос об амортизированном времени, тогда ответ будет равен O (1). Другой способ сказать это, что стоимость n добавлений - O (n).
Как это может быть? Каждое добавление O (n), но n из них также требует O (n). Это красота амортизации. Для простоты, скажем, массив начинается с размера 1 и растет в 2 раза каждый раз, когда он заполняется, поэтому мы всегда копируем силу из двух элементов. Это означает, что стоимость роста равна 1 в первый раз, второй - во второй раз и т. Д. В общем случае общая стоимость выращивания до n элементов равна TC = 1 + 2 + 4 + ... n. Ну, нетрудно видеть, что TC = 2n-1. Например. если n = 8, то TC = 1 + 2 + 4 + 8 = 15 = 2 * 8-1. Таким образом, TC равен , пропорциональному n или O (n).
Этот анализ работает независимо от того, начального размера массива или фактор роста, до тех пор, как фактор больше 1.
Если учитель хорошо, он или она задала этот вопрос в двусмысленном образом посмотрите, можете ли вы обсудить оба ответа.
Чтобы увеличить размер массива, вы не можете просто «добавить больше в конец», потому что вы скорее получите ошибку «segmentation fault». Так что даже если в качестве среднего значения требуется θ(1) шагов, потому что у вас достаточно места, если у вас есть O нотация O(n), потому что вам нужно скопировать старый массив в новый большой массив (для которого вы выделили память), и это должно занять n шагов ...в общем. С другой стороны, конечно, вы можете копировать массивы быстрее, потому что это всего лишь копия памяти из непрерывного пространства, и это должно быть 1 шаг в лучшем сценарии, то есть где страница (ОС) может принимать весь массив. В конечном счете ... математически, даже учитывая, что мы делаем шаги n/(4096 * 2^10) (4 КБ), это все равно означает сложность O(n).