Какая space complexity у данного алгоритма?

Прохожу кое-какие образовательные модули на 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). Кому верить?)
  • Вопрос задан
  • 216 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Не спрашивайте у чатжпт ничего, в чем не являетесь полным экспертом. Он почти в половине случаев выдает очень правдоподобный бред.

У этого алгоритма действительно пространственная сложность O(N) (если N - размер входного массива). Однако, можно натянуть сову на глобус, если отдельно считать входные и выходные данные (которых O(N)). Тогда можно сказать, что алгоритм использует O(1) дополнительно пространства. Входные и выходные данные все равно понадобятся, поэтому иногда их не считают.

У меня нет доступа к этому видео. Если они там говорят "additional space is O(1)", то это именно так, как я описал выше.
Ответ написан
Den4xCode
@Den4xCode
Coder
Создание массива не делает сложность равной О(N), это происходит потому что ты используешь цикл for и его сложность действительно O(N), что означает что он делает N операций, О(1) означает, что каждая такая операция будет совершена за константное время, что в случае с массивом очень быстро. chatGPT не панацея, он иногда тупит с ответами)
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы