Прохожу кое-какие образовательные модули на leetcode, и столкнулся с одной непонятной штукой.
(
на этой странице в видео, примерно ~4:00)
Они приводят такой пример на Java, и утверждают, что временная сложность этого алгоритма - O(N), а пространственная - O(1).
class Solution {
public int[] runningSum(int[] nums) {
int[] results = new int[nums.length]
results[0] = nums[0]
for (int i = 1; i < nums.length; i++) {
results[i] = nums[i] + results[i - 1]
}
return results
}
}
В отношении пространственной сложности - разве это действительно так? Ведь мы создаем дополнительный массив results с неопределенной длиной, что делает пространственную сложность равной O(N). В моем понимании, пространственная сложность была бы O(1), если бы мы не создавали дополнительных структур данных для результирующего массива, а преобразовали бы исходный массив на месте. Или я неправильно понимаю идею пространственной сложности?
Причем я сначала спросил у chat gpt, только я привел такой пример на typescript (как мне кажется, эквивалентный):
function runningSum(nums: number[]): number[] {
const result: number[] = Array.from({ length: nums.length })
nums.forEach((num, i) => result[i] = num + (result[i - 1] || 0))
return result
};
И ответ был, что пространственная сложность - O(N). Когда я подсунул ему тот же пример на Java - он тоже сказал, что и это O(N). Кому верить?)
Простой