Мне интересно, меняет ли изменчивость размера отдельных элементов входного массива функции то, как мы представляем ее пространственную сложность. Если у нас есть алгоритм, который принимает массив и создает новый массив со слегка измененным каждым элементом (чтобы не копировать указатели и фактически не хранить что-то новое в оперативной памяти), мне кажется логичным представить его пространственную сложность как O(n * k), где n — длина входного массива, а k — размер самого большого элемента в этом массиве.
Отбросим ли мы этот k, если он константа, т. е. размеры элементов в массив однороден (например, массив содержит только целые числа)? Или мы всегда отбрасываем его, даже если элементы различаются по размеру (например, если массив содержит строки разной длины)? Или мы никогда не отбрасываем его?
И чтобы сделать мой вопрос более конкретным, какова пространственная сложность этих двух функций:
function getModifiedNumberArray(numArr: number[]): number[] {
const newNumArr: number[] = []
for (let num of numArr) {
newNumArr.push(num + 1)
}
return newNumArr
}
function getModifiedStringArray(stringArr: string[]): string[] {
const newStringArr: string[] = []
for (let string of stringArr) {
newStringArr.push(string + '1')
}
return newStringArr
}
Подробнее здесь: https://stackoverflow.com/questions/798 ... input-type
